Գտեք Lucky Integer- ը զանգվածի Leetcode լուծման մեջ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Microsoft
Դասավորություն

Խնդրի հայտարարություն

«Մի զանգվածում գտեք բախտավոր ամբողջ թվին» խնդրի մեջ մեզ տրված է դասավորություն որտեղ ամբողջ թիվը կոչվում է բախտավոր, եթե զանգվածում դրա հաճախականությունը հավասար է իր արժեքին:

Մեր խնդիրն է վերադարձնել ամենամեծ հաջողակ համարը: Եթե ​​այդպիսի թիվ գոյություն չունի, մենք պետք է վերադարձնենք -1: Rayանգվածի արժեքները 1-ից 500-ի սահմաններում են, և զանգվածի երկարությունը առավելագույնը 500 է:

Օրինակ

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

բացատրություն:

Գտեք Lucky Integer- ը զանգվածի Leetcode լուծման մեջ

2-ի հաճախականությունը 2 է, իսկ 3-ի և 1-ի հաճախությունը `2-ը: Քանի որ XNUMX-ը միակ բախտավոր ամբողջ թիվն է, ուստի սա է մեր պատասխանը:

Տեսակավորելու մոտեցումը Array Leetcode լուծման մեջ Find Lucky Integer

Քանի որ մենք ուզում ենք հաշվել յուրաքանչյուր թվի դեպքերի քանակը, ապա գտնել տվյալ պայմանը բավարարող ամենամեծ տարրը: Դա անելու համար մենք կընտրենք մի շարք, այնուհետև կանցկացնենք ամբողջ զանգվածը `դրա դեպքերը հաշվելու համար, ապա ընտրելով պայմանը բավարարող ամենամեծ տարրը: Այստեղ մենք պետք է նետենք ամբողջական զանգվածը n անգամ, որպեսզի ժամանակի բարդությունը դառնա O (n * n): Մենք կարող ենք բարձրացնել կատարումը ՝ տեսակավորելով զանգվածը: Սա նույն թվերը կհամախմբի իրար: Մենք հետևելու ենք հետևյալ քայլերին.

  1. Տեսակավորել զանգվածը նվազման կարգով:
  2. Հաշվեք հանդիպած տարրի բոլոր դեպքերը, եթե այն բավարարում է պայմանը, ապա վերադարձեք այն:
  3.  Ի վերջո, եթե ոչ մի տարր չի բավարարում պայմանը, ապա վերադարձիր -1:

Իրականացման

C ++ ծածկագիր զանգվածում գտնելու համար Lucky Integer- ին

#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

Javaանգվածի մեջ գտնել Lucky Integer- ի համար Java կոդ

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

Lանգվածի Leetcode լուծման մեջ գտնելու Lucky Integer- ի բարդության վերլուծություն

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (nlogn) քանի որ մենք տեսակավորում ենք տրված զանգվածը: Այստեղ n- ը տրված զանգվածի երկարությունն է:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխանը պահելու համար օգտագործում ենք միայն փոփոխական:

Ashանգվածային Leetcode լուծման մեջ գտնելու համար Hashing մոտեցում գտնելու Lucky Integer- ին

Կարող ենք մեկ թեքով հաշվել յուրաքանչյուր թվի առաջացումը, նույնիսկ առանց տեսակավորելու `խաշման միջոցով: Մենք հետևելու ենք հետևյալ քայլերին.

  1. Ստեղծեք 501 չափի հաճախականության զանգված, քանի որ տարրի արժեքը կարող է լինել առավելագույնը 500:
  2. Անցեք տրված զանգվածը ամբողջական և պահեք յուրաքանչյուր տարրի քանակը հաճախականության զանգվածում:
  3. Այժմ անցեք հաճախականության զանգվածը վերջից և եթե որևէ տարր բավարարում է պայմանը, ապա վերադարձեք այն:
  4.  Ի վերջո, եթե ոչ մի տարր չի բավարարում պայմանը, ապա վերադարձիր -1:

Իրականացման

C ++ ծածկագիր զանգվածում գտնելու համար Lucky Integer- ին

#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

Javaանգվածի մեջ գտնել Lucky Integer- ի համար Java կոդ

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

Lանգվածի Leetcode լուծման մեջ գտնելու Lucky Integer- ի բարդության վերլուծություն

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք միայն մեկ անգամ ենք անցնում տրված զանգվածը: Այստեղ n- ը տրված զանգվածի երկարությունն է:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է O (n) քանի որ մենք ստեղծում ենք հեշ սեղան:

Սայլակ