Çatışmayan Nömrə Leetcode Həlli

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

The Çatışmayan Nömrə LeetCode Həlli – “İtkin Nömrə” bir sıra verildiyini bildirir ölçü n olan n fərqli nömrəs arasında [0,n]. olan nömrəni qaytarmalıyıq itkin diapazonda.

Misal:

Pin

 

Input:  nums = [3,0,1]

Output: 2

Explanation:

• Biz asanlıqla müşahidə edə bilərik ki, 0,3 rəqəmindən başqa [2] arasındakı bütün rəqəmlər mövcuddur.
• Beləliklə, 2-dir itkin nömrə [0,3] diapazonunda.

Input:  nums = [9,6,4,2,3,5,7,0,1]

Output: 8

Explanation:

• 8-dən başqa bütün rəqəmlər [0,9] diapazonu üçün massivdə mövcuddur.
• Beləliklə, 8-dir itkin nömrə [0,9] diapazonunda.

Yanaşma

Idea:

1. Bu problemi effektiv şəkildə həll etməyin bir çox yolu var, lakin biz burada müzakirə edəcəyik Vaxtında və O(1) Məkan istifadə edərək həll Bit manipulyasiya.
2. Qoy xo olmaq bitwise [0,9] diapazonunda olan bütün ədədlərin və giriş massivinin bütün elementlərinin xor. Biz asanlıqla müşahidə edə bilərik ki, çatışmayan ədəddən (tezlik = 1) başqa bütün elementlərin tezliyi 2 olacaq.
3. Həmçinin, biz bilirik ki, ədədin özü ilə bit istiqamətində xor həmişə sıfırdır. Beləliklə, tezliyi 2 olan bütün elementlər bit istiqamətində sıfır olaraq xor verəcək və çatışmayan nömrə olduğu kimi qalacaq (tezlik = 1 olduğundan).
4. Nəhayət, xo cavabımız kimi çatışmayan nömrəni saxlayacaq [0,n] diapazonunda olan bütün ədədlərin və giriş massivinin bütün elementlərinin bit istiqamətində xor götürdükdə.

Kodu

Eksik Nömrə Leetcode Həlli üçün C++ kodu:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size(),xo = n;
        for(int i=0;i<n;i++){
            xo^=i;
            xo^=nums[i];
        }
        return xo;
    }
};

Yarımçıq Nömrə Leetcode Həlli üçün Java kodu:

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length,xo = n;
        for(int i=0;i<n;i++){
            xo^=i;
            xo^=nums[i];
        }
        return xo;
    }
}

Yarımçıq Nömrə Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki biz döngəni tam olaraq n dəfə işlədirik, burada n = giriş massivinin ölçüsü.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz daimi boşluqdan istifadə edirik.

Referans: https://en.wikipedia.org/wiki/Bit_manipulation