अ‍ॅरे लीटकोड सोल्यूशनमध्ये लकी इंटिजर शोधा


अडचण पातळी सोपे
वारंवार विचारले मायक्रोसॉफ्ट
अरे

समस्या विधान

"अ‍ॅरेमध्ये लकी इंटिजर शोधा" या समस्येमध्ये आम्हाला एक दिले गेले आहे अॅरे अ‍ॅरे मधील त्याची वारंवारता त्याच्या मूल्याइतकी असल्यास पूर्णांक भाग्यवान असे म्हणतात.

आमचे कार्य म्हणजे सर्वात मोठी भाग्यवान संख्या परत करणे. अशी संख्या नसल्यास आम्हाला -1 परत करावे लागेल. अ‍ॅरे मधील मूल्ये 1 आणि 500 ​​दरम्यान असतात आणि अ‍ॅरेची लांबी कमाल 500 असते.

उदाहरण

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

स्पष्टीकरण:

अ‍ॅरे लीटकोड सोल्यूशनमध्ये लकी इंटिजर शोधा

2 ची वारंवारिता 2 आहे आणि 3 आणि चार ची वारंवारता 1 आहे. 2 हा केवळ भाग्यवान पूर्णांक आहे म्हणून हे आपले उत्तर आहे.

अ‍ॅरे लीटकोड सोल्यूशनमध्ये लकी इंटिजर शोधण्यासाठी दृष्टीकोन क्रमवारी लावत आहे

आम्हाला प्रत्येक संख्येच्या घटनांची संख्या मोजायची आहे आणि नंतर दिलेली अट पूर्ण करणारे सर्वात मोठे घटक सापडतात. हे करण्यासाठी आम्ही एक संख्या निवडू आणि नंतर त्यातील घटना मोजण्यासाठी संपूर्ण अ‍ॅरे पुढे जाईल आणि नंतर परिस्थितीत समाधानी असणारा सर्वात मोठा घटक निवडा. येथे आपल्याला पूर्ण अ‍ॅरे 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

अ‍ॅरे लीटकोड सोल्यूशनमध्ये लकी इंटिजर शोधा याचे जटिल विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे O (n) कारण आम्ही दिलेल्या अ‍ॅरेला फक्त एकदाच ट्रॉवर करत आहोत. येथे n दिलेली अ‍ॅरेची लांबी आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे O (n) कारण आपण हॅश टेबल बनवत आहोत.

संदर्भ