ਐਕਸ ਐਲੀਮੈਂਟਸ ਗ੍ਰੇਟਰ ਥਾਨ ਜਾਂ ਸਮਾਨ ਐਕਸ ਲੀਟਕੋਡ ਹੱਲ ਨਾਲ ਵਿਸ਼ੇਸ਼ ਐਰੇ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਗੂਗਲ
ਅਰੇ ਹੈਸ਼ਿੰਗ

ਸਮੱਸਿਆ ਵਿਚ, “ਐਕਸ ਐਲੀਮੈਂਟਸ ਗ੍ਰੇਟਰ ਥਾਨ ਜਾਂ ਇਕੁਅਲ ਐਕਸ ਨਾਲ ਸਪੈਸ਼ਲ ਐਰੇ”, ਸਾਨੂੰ ਇਕ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ ਐਰੇ ਗੈਰ-ਨਕਾਰਾਤਮਕ ਪੂਰਨ ਅੰਕ ਦੇ. ਸਾਨੂੰ ਕੁਝ ਪੂਰਨ ਅੰਕ ਐਕਸ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਕਿ ਐਰੇ ਵਿੱਚ ਇਸਦੇ ਬਰਾਬਰ ਦੇ ਬਰਾਬਰ X ਤੱਤ ਹੁੰਦੇ ਹਨ. ਜੇ ਇਸ ਸਥਿਤੀ ਨੂੰ ਪੂਰਾ ਕਰਨ ਵਾਲਾ ਕੋਈ ਸੰਭਵ ਐਕਸ ਨਹੀਂ ਹੈ, ਤਾਂ ਸਾਨੂੰ ਆਉਟਪੁੱਟ -1 ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਉਦਾਹਰਨ

1 2 3 4
-1
1 3 4 5
3

ਪਹੁੰਚ (ਬਰੂਟ ਫੋਰਸ)

ਇਹ ਨਿਸ਼ਚਤ ਹੈ ਕਿ ਜੇ ਕੋਈ ਹੱਲ X ਹੈ, ਤਾਂ ਐਕਸ ਹਮੇਸ਼ਾ ਵਿਲੱਖਣ ਰਹੇਗਾ.

ਸਬੂਤ:

ਇਸ ਤੇ ਵਿਚਾਰ ਕਰੋ ਕਿ X ਅਤੇ Y ਦੇ ਦੋ ਹੱਲ ਹਨ ਜਿਵੇਂ ਕਿ X! = Y. ਮੰਨ ਲਓ X <Y. ਹੁਣ, X ਤੋਂ ਵੱਧ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਦੇ ਤੱਤ ਦੀ ਗਿਣਤੀ X ਹੋਣੀ ਚਾਹੀਦੀ ਹੈ ਕਿਉਂਕਿ ਅਸੀਂ ਇਸਨੂੰ ਇੱਕ ਹੱਲ ਸਮਝਦੇ ਹਾਂ. ਪਰ, ਕਿਉਂਕਿ Y> X, ਇੱਥੇ X ਤੋਂ ਵੀ ਵੱਧ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ Y ਤੱਤ ਹਨ ਜਿਵੇਂ ਕਿ X! = Y. ਇਸ ਲਈ X ਦਾ ਹੱਲ ਹੋਣ ਦੀ ਸਾਡੀ ਧਾਰਨਾ ਗ਼ਲਤ ਹੈ ਜਦੋਂ ਤੱਕ X ਅਤੇ Y ਬਰਾਬਰ ਨਹੀਂ ਹੁੰਦੇ.

ਇਸ ਲਈ, ਹਮੇਸ਼ਾਂ ਵਿਲੱਖਣ ਹੱਲ ਹੁੰਦਾ ਹੈ, ਜੇ ਕੋਈ ਹੱਲ ਮੌਜੂਦ ਹੈ. ਹੁਣ, ਇਹ ਵੀ ਸਿੱਟਾ ਕੱ canਿਆ ਜਾ ਸਕਦਾ ਹੈ ਕਿ ਜੇ ਐਕਸ ਇਕ ਹੱਲ ਹੈ, ਤਾਂ ਇਸ ਦੇ ਬਰਾਬਰ / ਬਰਾਬਰ ਦੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ = ਐਕਸ, ਜੋ N ਤੋਂ ਘੱਟ ਹੋਣੀ ਚਾਹੀਦੀ ਹੈ, ਜਿਥੇ ਐ = ਐਰੇ ਦਾ ਆਕਾਰ (ਸੰਭਵ ਤੌਰ ਤੇ ਤੱਤਾਂ ਦੀ ਵੱਧ ਤੋਂ ਵੱਧ ਗਿਣਤੀ) = ਐਨ).

ਇਸ ਲਈ, ਜੇ ਕੋਈ ਹੱਲ X ਮੌਜੂਦ ਹੈ, ਤਾਂ ਇਹ [1, N] ਦੀ ਸੀਮਾ ਵਿੱਚ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ.

ਅਸੀਂ ਸੀਮਾ [1, N] ਵਿਚਲੇ ਹਰੇਕ ਪੂਰਨ ਅੰਕ ਦੀ ਜਾਂਚ ਕਰ ਸਕਦੇ ਹਾਂ ਜੇ ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਜੋ ਸੀਮਾ ਵਿਚਲੇ ਕਿਸੇ ਪੂਰਨ ਅੰਕ ਨਾਲੋਂ ਵੱਧ ਜਾਂ ਉਸ ਦੇ ਬਰਾਬਰ ਹੈ ਤਾਂ ਉਹ ਉਸ ਪੂਰਨ ਅੰਕ ਦੇ ਬਰਾਬਰ ਹੈ. ਉਦਾਹਰਣ ਦੇ ਲਈ, ਐਰੇ = {1, 3, 4, 5 consider ਤੇ ਵਿਚਾਰ ਕਰੋ. ਹੁਣ, 1 ਅਤੇ 2 ਵਿਚ ਐਰੇ ਵਿਚ ਕ੍ਰਮਵਾਰ 4 ਅਤੇ 3 ਐਲੀਮੈਂਟਸ ਵੱਡੇ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਹਨ. 3 ਤੋਂ ਵੱਧ ਦੇ ਬਰਾਬਰ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ 3 = 3. ਤਾਂ, 1 ਇਕੋ ਇਕ ਹੱਲ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਸੀਮਾ ਦੇ ਹਰੇਕ ਪੂਰਨ ਅੰਕ ਨਾਲੋਂ ਵਧੇਰੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਨੂੰ ਲੱਭਣ ਲਈ ਪੂਰੇ ਰੁੱਖ ਨੂੰ ਪਾਰ ਕਰਦੇ ਹਾਂ: [XNUMX, ਐਨ], ਇਹ ਪਹੁੰਚ ਹੌਲੀ ਹੈ.

ਐਲਗੋਰਿਥਮ

  1. ਹੱਲ ਦੀ ਜਾਂਚ ਕਰਨ ਲਈ i = 1 ਤੋਂ i = N ਤੱਕ ਇੱਕ ਲੂਪ ਚਲਾਓ:
    • 'ਜਾਂ' ਦੇ ਬਰਾਬਰ ਤੱਤ ਦੀ ਗਿਣਤੀ ਕਰੋ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

ਐਕਸ ਐਲੀਮੈਂਟਸ ਗ੍ਰੇਟਰ ਥਾਨ ਜਾਂ ਇਕਸਾਰ ਐਕਸ ਲੀਟਕੋਡ ਹੱਲ ਨਾਲ ਵਿਸ਼ੇਸ਼ ਐਰੇ ਦਾ ਗੁੰਝਲਦਾਰਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ * ਐਨ), ਐਨ = ਐਰੇ ਦਾ ਆਕਾਰ. ਸਭ ਤੋਂ ਬੁਰੀ ਸਥਿਤੀ ਵਿੱਚ, ਜਦੋਂ ਐਕਸ = ਐਨ ਹੱਲ ਹੈ, ਅਸੀਂ ਓ (ਐਨ * ਐਨ) ਦੀ ਤੁਲਨਾ ਕਰਦੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1). ਸਿਰਫ ਨਿਰੰਤਰ ਮੈਮੋਰੀ ਸਪੇਸ ਵਰਤੀ ਜਾਂਦੀ ਹੈ.

ਪਹੁੰਚ (ਅਨੁਕੂਲ)

ਅਸੀਂ ਇੱਕ ਐਰੇ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ, ਸਾਰਣੀ ਦੇ ਸਾਰੇ ਤੱਤਾਂ ਦੀ ਮੌਜੂਦਗੀ ਦੀ ਗਿਣਤੀ ਨੂੰ ਇੱਕ ਟੇਬਲ ਵਿੱਚ ਸਟੋਰ ਕਰ ਸਕਦੇ ਹਾਂ. ਨੋਟ ਕਰੋ ਕਿ N ਤੋਂ ਵੱਧ ਮੁੱਲ ਵਾਲੇ ਕਿਸੇ ਵੀ ਤੱਤ ਲਈ, ਅਸੀਂ ਇਸਨੂੰ ਮੁੱਲ N ਦੇ ਨਾਲ ਇੱਕ ਐਲੀਮੈਂਟ ਦੀ ਮੌਜੂਦਗੀ ਵਜੋਂ ਗਿਣ ਸਕਦੇ ਹਾਂ ਕਿਉਂਕਿ ਹੱਲ ਦਾ ਵੱਧ ਤੋਂ ਵੱਧ ਮੁੱਲ N ਹੋ ਸਕਦਾ ਹੈ.

ਹੁਣ, ਐਕਸ ਤੋਂ ਵੱਡਾ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਦੇ ਤੱਤ ਦੀ ਬਾਰੰਬਾਰਤਾ, ਐਕਸ ਦੇ ਸਾਰੇ ਤੱਤ ਦੀ ਐਕਸ + ਬਾਰੰਬਾਰਤਾ .

ਸੋ, ਐਰੇ ਵਿਚਲੇ ਹਰੇਕ ਪੂਰਨ ਅੰਕ ਲਈ, ਸਾਨੂੰ ਸੈੱਟ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਬਾਰੰਬਾਰਤਾ [i] = ਬਾਰੰਬਾਰਤਾ [i] + ਬਾਰੰਬਾਰਤਾ [i + 1], ਹਰ 'ਲਈi'ਸੀਮਾ ਵਿੱਚ [N - 1, 1], ਜੋ ਕਿ ਇੱਕ ਪਿਛੇਤਰ ਬਾਰੰਬਾਰਤਾ ਐਰੇ ਬਣਾਏਗਾ, ਇਸਦੇ ਤੱਤ ਦੀ ਸੰਖਿਆ ਨੂੰ ਵੱਡਾ ਜਾਂ ਬਰਾਬਰ ਰੱਖ ਦੇਵੇਗਾ 'i'  as ਬਾਰੰਬਾਰਤਾ [i].

ਹੁਣ, ਲੁਕਿੰਗ ਟੇਬਲ ਦੇ ਕਾਰਨ, ਅਸੀਂ ਅੰਦਰ [1, N] ਵਿਚਲੀ ਸੀਮਾ ਦੇ ਕਿਸੇ ਪੂਰਨ ਅੰਕ ਦੇ ਹੱਲ ਲਈ ਜਾਂਚ ਕਰ ਸਕਦੇ ਹਾਂ ਓ (1) ਸਮਾਂ. ਇਹ ਇੱਕ ਅਜਿਹਾ ਕੇਸ ਹੈ ਜਿੱਥੇ ਅਸੀਂ ਹਾਂ ਵਪਾਰ ਬੰਦ ਸਮੇਂ ਸਿਰ ਸੁਧਾਰ ਕਰਨ ਲਈ ਯਾਦਦਾਸ਼ਤ. ਕਿਉਂਕਿ ਟੇਬਲ N ਅਕਾਰ ਦਾ ਹੈ, ਇਸ ਲਈ ਸਾਨੂੰ ਯਾਦਦਾਸ਼ਤ ਦੀਆਂ ਸੀਮਾਵਾਂ ਦੀ ਕੋਈ ਚਿੰਤਾ ਨਹੀਂ ਹੈ.

 

ਐਕਸ ਐਲੀਮੈਂਟਸ ਗ੍ਰੇਟਰ ਥਾਨ ਜਾਂ ਸਮਾਨ ਐਕਸ ਲੀਟਕੋਡ ਹੱਲ ਨਾਲ ਵਿਸ਼ੇਸ਼ ਐਰੇ

ਐਲਗੋਰਿਥਮ

  1. ਅਰੰਭ ਕਰੋ ਏ ਬਾਰੰਬਾਰਤਾ ਅਕਾਰ N ਦੀ ਐਰੇ, ਹਰੇਕ ਮੁੱਲ ਦੇ ਹੋਣ ਦੇ ਨਾਲ ਜ਼ੀਰੋ
  2. ਹਰ ਤੱਤ ਲਈ i  ਐਰੇ ਵਿੱਚ:
    1. If i > ਐਨ, ਵਾਧੇ ਦੀ ਬਾਰੰਬਾਰਤਾ [ਐਨ]
    2. ਵਾਧਾ ਬਾਰੰਬਾਰਤਾ [i]
  3. ਤੋਂ ਇੱਕ ਪਿਛੇਤਰ ਦੀ ਰਕਮ ਬਣਾਓ ਬਾਰੰਬਾਰਤਾ ਜਿਵੇਂ:
    1. ਤੋਂ ਲੈਕੇ ਹਰ ਤੱਤ ਲਈ i = ਐਨ - 1 ਨੂੰ i = 0
      1. ਸੈੱਟ ਬਾਰੰਬਾਰਤਾ [i] = ਬਾਰੰਬਾਰਤਾ [i] + ਬਾਰੰਬਾਰਤਾ [i + 1]
  4. ਤੋਂ ਲੂਪ ਚਲਾਓ i = 1 ਤੋਂ i = N
    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

ਐਕਸ ਐਲੀਮੈਂਟਸ ਗ੍ਰੇਟਰ ਥਾਨ ਜਾਂ ਇਕਸਾਰ ਐਕਸ ਲੀਟਕੋਡ ਹੱਲ ਨਾਲ ਵਿਸ਼ੇਸ਼ ਐਰੇ ਦਾ ਗੁੰਝਲਦਾਰਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਐਨ = ਐਰੇ ਦਾ ਆਕਾਰ. ਅਸੀਂ ਓ (1) ਸਮੇਂ ਵਿਚ ਕਿਸੇ ਪੂਰਨ ਅੰਕ ਦੀ ਜਾਂਚ ਕਰ ਸਕਦੇ ਹਾਂ, ਇਸ ਲਈ ਸਭ ਤੋਂ ਮਾੜੇ ਹਾਲਾਤ ਵਿਚ ਅਸੀਂ ਓ (ਐਨ) ਸਮੇਂ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ). ਲੀਨੀਅਰ ਮੈਮੋਰੀ ਸਪੇਸ ਫ੍ਰੀਕੁਐਂਸੀ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਵਰਤੀ ਜਾਂਦੀ ਹੈ.