ಎಕ್ಸ್ ಎಲಿಮೆಂಟ್ಸ್ ಗ್ರೇಟರ್ ದ್ಯಾನ್ ಅಥವಾ ಈಕ್ವಲ್ ಎಕ್ಸ್ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದೊಂದಿಗೆ ವಿಶೇಷ ಅರೇ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗೂಗಲ್
ಅರೇ ಹ್ಯಾಶಿಂಗ್

ಸಮಸ್ಯೆಯಲ್ಲಿ, “ಎಕ್ಸ್ ಎಲಿಮೆಂಟ್ಸ್ ಗ್ರೇಟರ್ ದ್ಯಾನ್ ಅಥವಾ ಈಕ್ವಲ್ ಎಕ್ಸ್ ವಿತ್ ಸ್ಪೆಷಲ್ ಅರೇ”, ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಸರಣಿ ನಕಾರಾತ್ಮಕವಲ್ಲದ ಪೂರ್ಣಾಂಕಗಳ. ನಾವು ಕೆಲವು ಪೂರ್ಣಾಂಕ X ಅನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು, ಅಂದರೆ ಶ್ರೇಣಿಯಲ್ಲಿ ನಿಖರವಾಗಿ X ಅಂಶಗಳು ಹೆಚ್ಚು ಅಥವಾ ಸಮನಾಗಿವೆ. ಈ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುವ ಯಾವುದೇ ಎಕ್ಸ್ ಇಲ್ಲದಿದ್ದರೆ, ನಾವು output ಟ್ಪುಟ್ -1 ಮಾಡಬೇಕಾಗುತ್ತದೆ.

ಪರಿವಿಡಿ

ಉದಾಹರಣೆ

1 2 3 4
-1
1 3 4 5
3

ಅಪ್ರೋಚ್ (ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ)

ಪರಿಹಾರ X ಇದ್ದರೆ ಅದು ನಿಶ್ಚಿತ ಎಕ್ಸ್ ಯಾವಾಗಲೂ ಅನನ್ಯವಾಗಿರುತ್ತದೆ.

ಪುರಾವೆ:

X ಮತ್ತು Y ಎಂಬ ಎರಡು ಪರಿಹಾರಗಳಿವೆ ಎಂದು ಪರಿಗಣಿಸಿ, ಅಂದರೆ X! = Y. X <Y ಅನ್ನು Let ಹಿಸೋಣ. ಈಗ, X ಗಿಂತ ದೊಡ್ಡದಾದ ಅಥವಾ ಸಮನಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆ X ಆಗಿರಬೇಕು, ಅದನ್ನು ನಾವು ಪರಿಹಾರವೆಂದು ಪರಿಗಣಿಸುತ್ತೇವೆ. ಆದರೆ, Y> X ರಿಂದ, X! = Y ನಂತಹ X ಗಿಂತ ದೊಡ್ಡದಾದ ಅಥವಾ ಸಮನಾದ Y ಅಂಶಗಳಿವೆ. ಆದ್ದರಿಂದ X ಮತ್ತು Y ಸಮಾನವಾಗದ ಹೊರತು X ಒಂದು ಪರಿಹಾರ ಎಂಬ ನಮ್ಮ umption ಹೆಯು ತಪ್ಪಾಗಿದೆ.

ಆದ್ದರಿಂದ, ಪರಿಹಾರವು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಯಾವಾಗಲೂ ಒಂದು ವಿಶಿಷ್ಟ ಪರಿಹಾರವಿದೆ. ಈಗ, ಎಕ್ಸ್ ಒಂದು ಪರಿಹಾರವಾಗಿದ್ದರೆ, ಅದಕ್ಕಿಂತ ದೊಡ್ಡದಾದ / ಸಮನಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆ = ಎಕ್ಸ್, ಅದು ಎನ್ ಗಿಂತ ಕಡಿಮೆಯಿರಬೇಕು, ಅಲ್ಲಿ ರಚನೆಯ ಎನ್ = ಗಾತ್ರ (ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಅಂಶಗಳಂತೆ) = ಎನ್).

ಆದ್ದರಿಂದ, ಪರಿಹಾರ X ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಅದು [1, N] ವ್ಯಾಪ್ತಿಯಲ್ಲಿರಬೇಕು.

ಶ್ರೇಣಿಯಲ್ಲಿನ ಯಾವುದೇ ಪೂರ್ಣಾಂಕಕ್ಕಿಂತ ದೊಡ್ಡದಾದ ಅಥವಾ ಸಮನಾಗಿರುವ ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ ಆ ಪೂರ್ಣಾಂಕಕ್ಕೆ ಸಮನಾಗಿದ್ದರೆ ನಾವು [1, N] ಶ್ರೇಣಿಯಲ್ಲಿನ ಪ್ರತಿ ಪೂರ್ಣಾಂಕವನ್ನು ಪರಿಶೀಲಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ಅರೇ = {1, 3, 4, 5 consider ಅನ್ನು ಪರಿಗಣಿಸಿ. ಈಗ, 1 ಮತ್ತು 2 ಕ್ರಮವಾಗಿ 4 ಮತ್ತು 3 ಅಂಶಗಳನ್ನು ರಚನೆಯಲ್ಲಿ ಅವರಿಗಿಂತ ಹೆಚ್ಚು ಅಥವಾ ಸಮನಾಗಿವೆ. 3 = 3 ಕ್ಕಿಂತ ದೊಡ್ಡದಾದ / ಸಮನಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಆದ್ದರಿಂದ, 3 ಮಾತ್ರ ಪರಿಹಾರವಾಗಿದೆ. ವ್ಯಾಪ್ತಿಯ ಪ್ರತಿಯೊಂದು ಪೂರ್ಣಾಂಕಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಇಡೀ ಮರವನ್ನು ಹಾದುಹೋಗುವುದರಿಂದ: [1, N], ಈ ವಿಧಾನವು ನಿಧಾನವಾಗಿರುತ್ತದೆ.

ಕ್ರಮಾವಳಿ

  1. ಪರಿಹಾರವನ್ನು ಪರೀಕ್ಷಿಸಲು i = 1 ರಿಂದ i = N ಗೆ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ:
    • 'ಗಿಂತ ಹೆಚ್ಚಿನ ಅಥವಾ ಸಮನಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಿi'ಶ್ರೇಣಿಯಲ್ಲಿ
      • ಎಣಿಕೆ ಸಮಾನವಾಗಿದ್ದರೆ 'i', ಹಿಂತಿರುಗಿ i
  2. ರಿಟರ್ನ್ -1;

ಎಕ್ಸ್ ಎಲಿಮೆಂಟ್ಸ್ ಗ್ರೇಟರ್ ದ್ಯಾನ್ ಅಥವಾ ಈಕ್ವಲ್ ಎಕ್ಸ್ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದೊಂದಿಗೆ ವಿಶೇಷ ರಚನೆಯ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;

int specialArray(vector <int> &a)
{
    int n = a.size() , counter = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        counter = 0;
        for(int j = 0 ; j < n ; j++)
            if(a[j] >= i)
                counter++;
        if(counter == i)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length , counter = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            counter = 0;
            for(int j = 0 ; j < n ; j++)
                if(a[j] >= i)
                    counter++;
            if(counter == i)
                return i;
        }
        return -1;
    }
}
3

ಎಕ್ಸ್ ಎಲಿಮೆಂಟ್ಸ್ ಗ್ರೇಟರ್ ಅಥವಾ ಈಕ್ವಲ್ ಎಕ್ಸ್ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದೊಂದಿಗೆ ವಿಶೇಷ ರಚನೆಯ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎನ್), N = ರಚನೆಯ ಗಾತ್ರ. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, X = N ಪರಿಹಾರವಾದಾಗ, ನಾವು O (N * N) ಹೋಲಿಕೆಗಳನ್ನು ಮಾಡುತ್ತೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1). ಸ್ಥಿರವಾದ ಮೆಮೊರಿ ಸ್ಥಳವನ್ನು ಮಾತ್ರ ಬಳಸಲಾಗುತ್ತದೆ.

ಅಪ್ರೋಚ್ (ಆಪ್ಟಿಮಲ್)

ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಬಳಸಿಕೊಂಡು ನಾವು ಎಲ್ಲಾ ಅಂಶಗಳ ಸಂಭವಿಸುವಿಕೆಯ ಸಂಖ್ಯೆಯನ್ನು ಕೋಷ್ಟಕದಲ್ಲಿ ಸಂಗ್ರಹಿಸಬಹುದು. N ಗಿಂತ ಹೆಚ್ಚಿನ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ಯಾವುದೇ ಅಂಶಕ್ಕಾಗಿ, ನಾವು ಅದನ್ನು N ಮೌಲ್ಯದೊಂದಿಗೆ ಒಂದು ಅಂಶದ ಸಂಭವ ಎಂದು ಪರಿಗಣಿಸಬಹುದು ಏಕೆಂದರೆ ದ್ರಾವಣದ ಗರಿಷ್ಠ ಮೌಲ್ಯವು N ಆಗಿರಬಹುದು.

ಈಗ, X ಗಿಂತ ಹೆಚ್ಚಿನ ಅಥವಾ ಸಮನಾದ ಅಂಶಗಳ ಆವರ್ತನ X ಗಿಂತ ಹೆಚ್ಚಿನ ಎಲ್ಲ ಅಂಶಗಳ X + ಆವರ್ತನದ X. ಆವರ್ತನ. [1, N] ವ್ಯಾಪ್ತಿಯ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಇದನ್ನು ಕಂಡುಹಿಡಿಯಲು, ನಾವು ಪ್ರತ್ಯಯ ಆವರ್ತನ ಶ್ರೇಣಿಯನ್ನು ಹೊಂದಿರಬೇಕು .

ಆದ್ದರಿಂದ, ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಪೂರ್ಣಾಂಕಕ್ಕೂ, ನಾವು ಹೊಂದಿಸಬೇಕಾಗಿದೆ ಆವರ್ತನ [i] = ಆವರ್ತನ [i] + ಆವರ್ತನ [i + 1], ಪ್ರತಿಯೊಬ್ಬರಿಗೂ 'i'ವ್ಯಾಪ್ತಿಯಲ್ಲಿ [N - 1, 1], ಇದು ಪ್ರತ್ಯಯ ಆವರ್ತನ ರಚನೆಯನ್ನು ರಚಿಸುತ್ತದೆ, ಹೆಚ್ಚಿನ ಅಥವಾ ಸಮನಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ 'i'  as ಆವರ್ತನ [i].

ಈಗ, ಲುಕಪ್ ಟೇಬಲ್ ಕಾರಣ, [1, N] ವ್ಯಾಪ್ತಿಯಲ್ಲಿರುವ ಯಾವುದೇ ಪೂರ್ಣಾಂಕಕ್ಕಾಗಿ ನಾವು ಪರಿಹಾರವನ್ನು ಪರಿಶೀಲಿಸಬಹುದು ಒ (1) ಸಮಯ. ಇದು ನಾವು ಇರುವ ಸಂದರ್ಭ ವ್ಯಾಪಾರ ಆಫ್ ಸಮಯಕ್ಕೆ ಸುಧಾರಿಸಲು ಮೆಮೊರಿ. ಟೇಬಲ್ ಗಾತ್ರ N ಆಗಿರುವುದರಿಂದ, ನಮಗೆ ಮೆಮೊರಿ ಮಿತಿಗಳ ಬಗ್ಗೆ ಯಾವುದೇ ಚಿಂತೆ ಇಲ್ಲ.

 

ಎಕ್ಸ್ ಎಲಿಮೆಂಟ್ಸ್ ಗ್ರೇಟರ್ ದ್ಯಾನ್ ಅಥವಾ ಈಕ್ವಲ್ ಎಕ್ಸ್ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದೊಂದಿಗೆ ವಿಶೇಷ ಅರೇ

ಕ್ರಮಾವಳಿ

  1. ಪ್ರಾರಂಭಿಸಿ a ಆವರ್ತನ ಗಾತ್ರದ N ನ ಶ್ರೇಣಿ, ಪ್ರತಿ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಶೂನ್ಯ
  2. ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ i  ಶ್ರೇಣಿಯಲ್ಲಿ:
    1. If i > ಎನ್, ಹೆಚ್ಚಳ ಆವರ್ತನ [ಎನ್]
    2. ಹೆಚ್ಚಳ ಆವರ್ತನ [i]
  3. ನಿಂದ ಪ್ರತ್ಯಯ ಮೊತ್ತ ರಚನೆಯನ್ನು ರಚಿಸಿ ಆವರ್ತನ ಹೀಗೆ:
    1. ರಿಂದ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ i = ಎನ್ - 1 ಗೆ i = 0
      1. ಸೆಟ್ ಆವರ್ತನ [i] = ಆವರ್ತನ [i] + ಆವರ್ತನ [i + 1]
  4. ನಿಂದ ಲೂಪ್ ಅನ್ನು ರನ್ ಮಾಡಿ i = 1 ರಿಂದ i = ಎನ್
    1. If i == ಆವರ್ತನ [i], ಹಿಂತಿರುಗಿ i
  5. ರಿಟರ್ನ್ -1

ಎಕ್ಸ್ ಎಲಿಮೆಂಟ್ಸ್ ಗ್ರೇಟರ್ ದ್ಯಾನ್ ಅಥವಾ ಈಕ್ವಲ್ ಎಕ್ಸ್ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದೊಂದಿಗೆ ವಿಶೇಷ ರಚನೆಯ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;

int specialArray(vector<int>& a)
{
    int n = a.size();
    vector <int> frequency(n + 1 , 0);
    for(int i = 0 ; i < n ; i++)
        if(a[i] > n)
            frequency[n]++;
        else
            frequency[a[i]]++;

    for(int i = n - 1 ; i >= 0 ; i--)
        frequency[i] += frequency[i + 1];

    for(int i = 0 ; i <= n ; i++)
        if(frequency[i] == i)
            return i;

    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length;
        int[] frequency = new int[n + 1];
        for(int i = 0 ; i < n ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < n ; i++)
            if(a[i] > n)
                frequency[n]++;
            else
                frequency[a[i]]++;

        for(int i = n - 1 ; i >= 0 ; i--)
            frequency[i] += frequency[i + 1];

        for(int i = 0 ; i <= n ; i++)
            if(frequency[i] == i)
                return i;

        return -1;
    }
}
3

ಎಕ್ಸ್ ಎಲಿಮೆಂಟ್ಸ್ ಗ್ರೇಟರ್ ಅಥವಾ ಈಕ್ವಲ್ ಎಕ್ಸ್ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದೊಂದಿಗೆ ವಿಶೇಷ ರಚನೆಯ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), N = ರಚನೆಯ ಗಾತ್ರ. ನಾವು ಒ (1) ಸಮಯದಲ್ಲಿ ಯಾವುದೇ ಪೂರ್ಣಾಂಕವನ್ನು ಪರಿಶೀಲಿಸಬಹುದು, ಆದ್ದರಿಂದ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಒ (ಎನ್) ಸಮಯವನ್ನು ಬಳಸುತ್ತೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್). ಆವರ್ತನಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಲೀನಿಯರ್ ಮೆಮೊರಿ ಸ್ಥಳವನ್ನು ಬಳಸಲಾಗುತ್ತದೆ.