ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਲੱਕੀ ਇੰਟੀਜ਼ਰ ਦਾ ਪਤਾ ਲਗਾਓ


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

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ ਵਿੱਚ "ਇੱਕ ਐਰੇ ਵਿੱਚ ਲੱਕੀ ਇੰਟੀਜਰ ਲੱਭੋ" ਸਾਨੂੰ ਇੱਕ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ ਐਰੇ ਜੇ ਪੂਰਨ ਅੰਕ ਨੂੰ ਭਾਗਸ਼ਾਲੀ ਕਿਹਾ ਜਾਂਦਾ ਹੈ ਜੇ ਐਰੇ ਵਿਚ ਇਸ ਦੀ ਬਾਰੰਬਾਰਤਾ ਇਸਦੇ ਮੁੱਲ ਦੇ ਬਰਾਬਰ ਹੈ.

ਸਾਡਾ ਕੰਮ ਸਭ ਤੋਂ ਵੱਡੀ ਖੁਸ਼ਕਿਸਮਤ ਨੰਬਰ ਵਾਪਸ ਕਰਨਾ ਹੈ. ਜੇ ਅਜਿਹੀ ਕੋਈ ਗਿਣਤੀ ਮੌਜੂਦ ਨਹੀਂ ਹੈ ਤਾਂ ਸਾਨੂੰ -1 ਵਾਪਸ ਕਰਨਾ ਪਏਗਾ. ਐਰੇ ਵਿੱਚ ਮੁੱਲ 1 ਅਤੇ 500 ਦੇ ਵਿਚਕਾਰ ਹੁੰਦੇ ਹਨ ਅਤੇ ਐਰੇ ਦੀ ਲੰਬਾਈ ਵੱਧ ਤੋਂ ਵੱਧ 500 ਹੁੰਦੀ ਹੈ.

ਉਦਾਹਰਨ

arr = [2,2,3,4]
2

ਕਥਾ:

ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਲੱਕੀ ਇੰਟੀਜ਼ਰ ਦਾ ਪਤਾ ਲਗਾਓ

2 ਦੀ ਬਾਰੰਬਾਰਤਾ 2 ਹੈ ਅਤੇ 3 ਅਤੇ ਚਾਰ ਦੀ ਬਾਰੰਬਾਰਤਾ 1 ਹੈ. ਜਿਵੇਂ ਕਿ 2 ਸਿਰਫ ਇਕ ਖੁਸ਼ਕਿਸਮਤ ਪੂਰਨ ਅੰਕ ਹੈ ਇਸ ਲਈ ਇਹ ਸਾਡਾ ਉੱਤਰ ਹੈ.

ਲੜੀ ਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਲੱਕੀ ਇੰਟੀਜਰ ਲਈ ਲੜੀਬੱਧ ਕਰਨਾ

ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਹਰ ਇੱਕ ਨੰਬਰ ਦੀ ਮੌਜੂਦਗੀ ਦੀ ਗਿਣਤੀ ਨੂੰ ਗਿਣਨਾ ਚਾਹੁੰਦੇ ਹਾਂ ਅਤੇ ਫਿਰ ਦਿੱਤੀ ਗਈ ਸ਼ਰਤ ਨੂੰ ਸੰਤੁਸ਼ਟ ਕਰਨ ਵਾਲਾ ਸਭ ਤੋਂ ਵੱਡਾ ਤੱਤ ਪਾਉਂਦੇ ਹਾਂ. ਅਜਿਹਾ ਕਰਨ ਲਈ ਅਸੀਂ ਇੱਕ ਨੰਬਰ ਚੁਣਾਂਗੇ ਅਤੇ ਫਿਰ ਇਸ ਦੀ ਮੌਜੂਦਗੀ ਨੂੰ ਗਿਣਨ ਲਈ ਪੂਰੀ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਾਂਗੇ ਅਤੇ ਫਿਰ ਸਥਿਤੀ ਨੂੰ ਸੰਤੁਸ਼ਟ ਕਰਨ ਵਾਲੇ ਸਭ ਤੋਂ ਵੱਡੇ ਤੱਤ ਦੀ ਚੋਣ ਕਰਾਂਗੇ. ਇੱਥੇ ਸਾਨੂੰ ਪੂਰੀ ਐਰੇ n ਟਾਈਮ ਨੂੰ ਪਾਰ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਤਾਂ ਜੋ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ O (n * n) ਬਣ ਜਾਵੇ. ਅਰੇ ਨੂੰ ਕ੍ਰਮਬੱਧ ਕਰਕੇ ਅਸੀਂ ਕਾਰਜਕੁਸ਼ਲਤਾ ਵਧਾ ਸਕਦੇ ਹਾਂ. ਇਹ ਇਕੋ ਜਿਹੇ ਨੰਬਰ ਲੈ ਕੇ ਆਵੇਗਾ. ਅਸੀਂ ਇਨ੍ਹਾਂ ਕਦਮਾਂ ਦੀ ਪਾਲਣਾ ਕਰਾਂਗੇ:

  1. ਘੱਟਦੇ ਕ੍ਰਮ ਵਿੱਚ ਐਰੇ ਨੂੰ ਕ੍ਰਮਬੱਧ ਕਰੋ.
  2. ਦਰਪੇਸ਼ ਤੱਤ ਦੀਆਂ ਸਾਰੀਆਂ ਘਟਨਾਵਾਂ ਗਿਣੋ ਜੇ ਇਹ ਸ਼ਰਤ ਨੂੰ ਪੂਰਾ ਕਰਦਾ ਹੈ ਤਾਂ ਇਸ ਨੂੰ ਵਾਪਸ ਕਰੋ.
  3.  ਅੰਤ ਵਿੱਚ, ਜੇ ਕੋਈ ਤੱਤ ਸ਼ਰਤ ਨੂੰ ਸੰਤੁਸ਼ਟ ਨਹੀਂ ਕਰਦਾ ਤਾਂ ਵਾਪਸ ਆਓ -1.

ਲਾਗੂ

ਲੁਕਵੀਂ ਪੂਰਨ ਅੰਕ ਲਈ ਐਰੇ ਲਈ ਸੀ ++ ਕੋਡ

#include <bits/stdc++.h> 
using namespace std; 
int findLucky(vector<int>& arr) {
    sort(begin(arr), end(arr), greater<int>());
    int cnt = 1;
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] == arr[i - 1])
            ++cnt;
        else {
            if (arr[i - 1] == cnt)
                return cnt;
            cnt = 1;
        }
    }
    return arr.back() == cnt ? cnt : - 1;
}

int main() 
{ 
vector<int> arr = {2,2,3,4}; 
 int ans=findLucky(arr);
 cout<<ans<<endl;
 return 0;
}
2

ਐਰੇ ਵਿੱਚ ਲੱਕੀ ਇੰਟੀਜ਼ਰ ਲਈ ਜਾਵਾ ਕੋਡ

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
public static int findLucky(int[] arr) {
    Arrays.sort(arr);
    int ans = 0;
    for (int i = arr.length - 1; i >= 0; i--) {
        ans++;
        if (i == 0 || arr[i] != arr[i - 1]) {
            if (ans == arr[i]) {
                return ans;
            }
            ans = 0;
        }
    }
    return -1;
}
  public static void main(String[] args) {
        int [] arr = {2,2,3,4}; 
        int ans=findLucky(arr); 
        System.out.println(ans);
  }
}
2

ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਲੱਕੀ ਲੱਕੀ ਇੰਟੀਜ਼ਰ ਦੀ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ

ਉਪਰੋਕਤ ਕੋਡ ਦੀ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਹੈ O (nlogn) ਕਿਉਂਕਿ ਅਸੀਂ ਦਿੱਤੀ ਗਈ ਐਰੇ ਨੂੰ ਛਾਂਟ ਰਹੇ ਹਾਂ. ਇੱਥੇ n ਦਿੱਤੀ ਗਈ ਐਰੇ ਦੀ ਲੰਬਾਈ ਹੈ.

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

ਉਪਰੋਕਤ ਕੋਡ ਦੀ ਸਪੇਸ ਗੁੰਝਲਤਾ ਹੈ ਓ (1) ਕਿਉਂਕਿ ਅਸੀਂ ਜਵਾਬ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਸਿਰਫ ਇੱਕ ਪਰਿਵਰਤਨ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ.

ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿਚ ਲੱਕੀ ਇੰਟਟੀਜਰ ਲੱਭਣ ਲਈ ਹੈਸ਼ਿੰਗ ਅਪ੍ਰੋਚ

ਅਸੀਂ ਹਰ ਨੰਬਰ ਦੀ ਮੌਜੂਦਗੀ ਨੂੰ ਹੈਸ਼ਿੰਗ ਦੀ ਸਹਾਇਤਾ ਨਾਲ ਛਾਂਟੀ ਕੀਤੇ ਬਗੈਰ ਇਕੋ ਸਮੇਂ ਵਿਚ ਗਿਣ ਸਕਦੇ ਹਾਂ. ਅਸੀਂ ਇਨ੍ਹਾਂ ਕਦਮਾਂ ਦੀ ਪਾਲਣਾ ਕਰਾਂਗੇ:

  1. 501 ਆਕਾਰ ਦੀ ਬਾਰੰਬਾਰਤਾ ਐਰੇ ਬਣਾਓ ਕਿਉਂਕਿ ਐਲੀਮੈਂਟ ਦਾ ਮੁੱਲ ਵੱਧ ਤੋਂ ਵੱਧ 500 ਹੋ ਸਕਦਾ ਹੈ.
  2. ਦਿੱਤੀ ਗਈ ਐਰੇ ਨੂੰ ਪੂਰਾ ਪਾਰ ਕਰੋ ਅਤੇ ਹਰ ਇਕਾਈ ਦੀ ਗਿਣਤੀ ਨੂੰ ਬਾਰੰਬਾਰਤਾ ਐਰੇ ਵਿਚ ਸਟੋਰ ਕਰੋ.
  3. ਹੁਣ ਅੰਤ ਤੋਂ ਬਾਰੰਬਾਰਤਾ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰੋ ਅਤੇ ਜੇ ਕੋਈ ਤੱਤ ਸ਼ਰਤ ਨੂੰ ਸੰਤੁਸ਼ਟ ਕਰਦਾ ਹੈ ਤਾਂ ਇਸਨੂੰ ਵਾਪਸ ਕਰ ਦਿਓ.
  4.  ਅੰਤ ਵਿੱਚ, ਜੇ ਕੋਈ ਤੱਤ ਸ਼ਰਤ ਨੂੰ ਸੰਤੁਸ਼ਟ ਨਹੀਂ ਕਰਦਾ ਤਾਂ ਵਾਪਸ ਆਓ -1.

ਲਾਗੂ

ਲੁਕਵੀਂ ਪੂਰਨ ਅੰਕ ਲਈ ਐਰੇ ਲਈ ਸੀ ++ ਕੋਡ

#include <bits/stdc++.h> 
using namespace std; 
int findLucky(vector<int>& arr) {
    int m[501] = {};
    for (auto n : arr)
        ++m[n];
    for (auto n = arr.size(); n > 0; --n)
        if (n == m[n])
            return n;
    return -1;
}

int main() 
{ 
vector<int> arr = {2,2,3,4}; 
 int ans=findLucky(arr);
 cout<<ans<<endl;
 return 0;
}
2

ਐਰੇ ਵਿੱਚ ਲੱਕੀ ਇੰਟੀਜ਼ਰ ਲਈ ਜਾਵਾ ਕੋਡ

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int findLucky(int[] arr) {
    int[] m = new int[501];
    for(int i=0;i<arr.length;i++)
        ++m[arr[i]];
    for (int n = arr.length; n > 0; --n)
        if (n == m[n])
            return n;
    return -1;
    }
  public static void main(String[] args) {
        int [] arr = {2,2,3,4}; 
        int ans=findLucky(arr); 
        System.out.println(ans);
  }
}
2

ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਲੱਕੀ ਲੱਕੀ ਇੰਟੀਜ਼ਰ ਦੀ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ

ਉਪਰੋਕਤ ਕੋਡ ਦੀ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਹੈ ਹੇ (n) ਕਿਉਂਕਿ ਅਸੀਂ ਦਿੱਤੀ ਗਈ ਐਰੇ ਨੂੰ ਸਿਰਫ ਇਕ ਵਾਰ ਟ੍ਰਾਂਸ ਕਰ ਰਹੇ ਹਾਂ. ਇੱਥੇ n ਦਿੱਤੀ ਗਈ ਐਰੇ ਦੀ ਲੰਬਾਈ ਹੈ.

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

ਉਪਰੋਕਤ ਕੋਡ ਦੀ ਸਪੇਸ ਗੁੰਝਲਤਾ ਹੈ ਹੇ (n) ਕਿਉਂਕਿ ਅਸੀਂ ਹੈਸ਼ ਟੇਬਲ ਬਣਾ ਰਹੇ ਹਾਂ.

ਹਵਾਲੇ