Bir sıra Leetcode həllində uğurlu tamsayı tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur microsoft
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 101

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Problemdə ”Bir massivdə Şanslı Tamsayı tapın” bizə verilir array massivdəki tezliyi dəyərinə bərabərdirsə, tam ədədin şanslı olduğu deyilir.

Bizim vəzifəmiz ən böyük şanslı nömrəni qaytarmaqdır. Belə bir nömrə yoxdursa, 1-i qaytarmalıyıq. Dizidəki dəyərlər 1 ilə 500 arasındadır və massivin uzunluğu maksimum 500-dür.

misal

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

Izahat:

Bir sıra Leetcode həllində uğurlu tamsayı tapınPin

2-nin tezliyi 2-dir, 3-ün və dördünün tezliyi 1-dir. 2 yeganə şanslı ədədi olduğu üçün cavabımız budur.

Bir sıra Leetcode həllində uğurlu tam ədədi tapmaq üçün çeşidləmə yanaşması

Hər sayın meydana gəlmə sayını hesablamaq və sonra verilən şərti təmin edən ən böyük elementi tapmaq istədiyimiz kimi. Bunu etmək üçün bir sıra seçəcəyik və sonra meydana gəlmələrini saymaq üçün bütün massivi gəzib daha sonra şərti təmin edən ən böyük elementi seçəcəyik. Burada zamanın mürəkkəbliyi O (n * n) olacağı üçün tam sıra n dəfə keçməliyik. Dizini sıralayaraq performansı artıra bilərik. Bu eyni rəqəmləri bir araya gətirəcəkdir. Bu addımları izləyəcəyik:

  1. Dizini azalan sırada sıralayın.
  2. Qarşılaşılan elementin şərtlərini təmin edərsə, bütün hadisələrini sayın və geri qaytarın.
  3.  Sonda, heç bir şərt şərti təmin etmirsə, -1 qaytarın.

Həyata keçirilməsi

Bir massivdə Lucky Tamsayı tapmaq üçün C ++ kodu

#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

Bir massivdə Lucky Tamsayı tapın üçün Java kodu

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

Bir sıra Leetcode həllində şanslı bir tam ədədi tapın

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (nlogn) çünki verilən serialı çeşidləyirik. Burada n verilən massivin uzunluğudur.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

Bir sıra Leetcode həllində uğurlu tamsayı tapmaq üçün Hashing yanaşması

Haşlama köməyi ilə çeşidlənmədən də hər sayın meydana çıxmasını bir anda saya bilərik. Bu addımları izləyəcəyik:

  1. Elementin dəyəri maksimum 501 ola biləcəyi üçün 500 ölçülü bir tezlik massivi yaradın.
  2. Verilən massivi tam keçin və hər elementin sayını tezlik massivində saxlayın.
  3. İndi tezlik massivini sondan keçin və hər hansı bir element şərti təmin edirsə, onu qaytarın.
  4.  Sonda, heç bir şərt şərti təmin etmirsə, -1 qaytarın.

Həyata keçirilməsi

Bir massivdə Lucky Tamsayı tapmaq üçün C ++ kodu

#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

Bir massivdə Lucky Tamsayı tapın üçün Java kodu

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

Bir sıra Leetcode həllində şanslı bir tam ədədi tapın

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki verilən serialı yalnız bir dəfə keçirik. Burada n verilən massivin uzunluğudur.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (n) çünki bir hash masa yaradırıq.

References

Crack Sistemi Dizayn Müsahibələri
Translate »
1