Sıralanmış Array LeetCode Həllində Çatışmayan Element

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:

Çeşidlənmiş Massivdə Çatışmayan Element LeetCode Həlli – Sıralanan nömrələrlə tam ədəd massivi verilmişdir. artan sifariş və onun bütün elementləri var unikal və həmçinin k tam ədədi verildikdə, k-ni qaytarınth massivin ən sol nömrəsindən başlayaraq əskik nömrə.

Misal:

Məsələn 1

Input: nums = [4,7,9,10], k = 3
Output: 8
Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8.

Məsələn 2

Input: nums = [4,7,9,10], k = 1
Output: 5
Explanation: The first missing number is 5.

 Məhdudiyyət:

Pin

Explanation:

• Massivin elementləri bunlardır unikal və sıralanır artan üçün.
• geri qaytarmalıyıq kth -dən başlayaraq əskik nömrə ən sol nömrə serialın.
• Yuxarıda misal 1, ən soldakı rəqəmdir 4
• Bir neçə çatışmayan nömrələr bunlardır:

                              1-ci çatışmayan nömrə: 5

                              2-ci çatışmayan nömrə: 6

                              3-cü çatışmayan nömrə: 8

Qeyd: 7 ədədlə mövcuddur, ona görə də 6-dan sonra növbəti çatışmayan rəqəm 8-dir

• Verilmiş məhdudiyyətdə ədədlər [i] arasında [1 ilə 10^7] və aralarındakı uzunluğun ədədləri [1 - 5*10^4].

Müşahidə:

Əgər müşahidə etsək, massivin sıralandığını görə bilərik artan sifariş vermək və tələb etmək kth çatışmayan nömrə. Deməli, istifadə edə biləcəyimiz ehtimal yüksəkdir İkili axtarış sualda.

Yanaşma:Pin

• Binary Search-də biz iki göstəricidən istifadə edirik startIndex (si) və endIndex(ei) və tapmaq orta İndeks (orta) [startIndex + (endIndex -startIdx)/2] sonra biz axtarış sahəsimizi daraldacağıq.

                                                                        [ si=0, ei=3 orta= 0 + (3-0)/2 ]

• Axtarış sahəsimizi necə daraldırıq? Bu suala cavab verməzdən əvvəl gəlin əvvəlcə ədədlər[0] ilə ədədlər[mid] arasında neçə əskik rəqəmin olduğunu necə öyrəndiyimizi müzakirə edək.

                                                 itkin elementlərin sayı = ədədlər[orta] – (orta+ədədlər[0]) = 7-(1+4) = 2

• Orta indeks-Element arasında [7] və ən sol element [4], yalnız 5 və 6 mövcud deyil ki, yalnız iki əskik nömrə var amma biz istəyirik 3rd çatışmayan nömrə.

 

Pin

• Yuxarıdakı şəkildə k-ci əskik nömrə üzərindədir  sağ tərəf  ya da deyə bilərik ki, K > çatışmayan element-saymaq deməli, edəcəyik artırmaq si =orta+1;
• Eynilə, əgər k<= itkin element-saymaq sonra köçürük azalma ei=orta-1;
• Bu şəkildə axtarış sahəsimizi daraldacağıq si<=ei
• Döngə bitdikdən sonra neçə element olduğunu öyrənəcək itirilmiş arasında nums[ei] və ən sol element  

                                                     itirilmiş=nums[ei]-(ən sol element +ei)

•   Nəhayət, bəzi elementlərin əskik olub olmadığını yoxlamaq lazımdır, sonra isə bu elementlər arasında fərq yaratmalıyıq kth itkin və itkin 

                         diff=k-itirdi

•  Qayıtmaq ədəd[ei]+fərq

KOD:

Sortlaşdırılmış Massivdə Çatışmayan Element ÜÇÜN JAVA KODU

class Solution {
    public int missingElement(int[] nums, int k) {
        int n=nums.length;
        int leftMost=nums[0];
        int si=0;
        int ei=n-1;
        while(si<=ei){
            int mid=si+(ei-si)/2;
            // missing element in b/w leftmost and nums[mid]
            int missingCount=nums[mid]-(leftMost+mid);
            if(missingCount<k){
                // potential answer on be right side
                si=mid+1;
            }
            else{
                // potential answer on be left side
                ei=mid-1;
            }
            
        }
        // After the end of loop  ei will be on correct position
        // nums[ei] can be our potential answer 
        //lostCount will contain How many elements we lost from leftMost
        int lostCount=nums[ei]-(leftMost+ei);
      // check how much element missed out on ei from leftMost k-lostedCount 
          int diff=k-lostCount;
        // add that diff in nums[ei]
        return nums[ei]+diff;
        
    }
}

Sorted Massivdə Çatışmayan Element ÜÇÜN C++ KODU

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
         int n=nums.size();
        int leftMost=nums[0];
        int si=0;
        int ei=n-1;
        while(si<=ei){
            int mid=si+(ei-si)/2;
            // missing element in b/w leftmost and nums[mid]
            int missingCount=nums[mid]-(leftMost+mid);
            if(missingCount<k){
                // potential answer on be right side
                si=mid+1;
            }
            else{
                // potential answer on be left side
                ei=mid-1;
            }
            
        }
        // After the end of loop  ei will be on correct position
        // nums[ei] can be our potential answer 
        //lostCount will contain How many elements we lost from leftMost
        int lostCount=nums[ei]-(leftMost+ei);
         // check how much element missed out on ei from leftMost k-lostedCount 
        int diff=k-lostCount;
        // add that diff in nums[ei]
        return nums[ei]+diff;
    }
};

Çeşidlənmiş massivdə çatışmayan element üçün mürəkkəblik təhlili LeetCode Həll:

Zamanın mürəkkəbliyi

O (logN)  istifadə etdiyimiz kimi İkili axtarış

Kosmik Mürəkkəblik 

O (1) çünki biz heç bir əlavə yerdən istifadə etmirik.