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

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Cisco Facebook Goldman Sachs google Intel microsoft Nvidia Kahin PayPal Salesforce
Geyim Bit manipulyasiya Dinamik proqramlaşdırma Sükut Riyaziyyat çeşidləyiciBaxılıb 106

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:

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

 

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ındaO(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

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