Meditasi LeetCode: Nombor Hilang

Mari kita mulakan dengan penerangan untuk masalah ini:

Memandangkan nombor tatasusunan yang mengandungi n nombor berbeza dalam julat [0, n], kembalikan satu-satunya nombor dalam julat yang tiada daripada tatasusunan.

Contohnya:

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

Atau:

Input: nums = [0, 1]
Output: 2

Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0, 2]. 2 is the missing number in the range since it does not appear in nums.

Atau:

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

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0, 9]. 8 is the missing number in the range since it does not appear in nums.

Ia juga menyatakan bahawa semua nombor nombor adalah unik.

---

Satu cara mudah untuk menyelesaikannya ialah mendapatkan jumlah keseluruhan julat, kemudian tolak jumlah tatasusunan yang diberikan. Apa yang tinggal ialah nombor yang hilang.

Ia boleh dilakukan menggunakan pengurangan untuk menjumlahkan nombor, seperti ini:

function missingNumber(nums: number[]): number {
  return Array.from({ 
    length: nums.length + 1 
  }, (_, idx) => idx).reduce((acc, item) => acc + item, 0) 
  - nums.reduce((acc, item) => acc + item, 0);
}

Mula-mula, kami mencipta tatasusunan dengan nilai dari 0 hingga nums.length 1 dan dapatkan jumlahnya, kemudian tolak jumlah nombor daripadanya.

Walau bagaimanapun, kerumitan masa dan ruang akan menjadi $O(n)$O(n) dengan penyelesaian ini semasa kami mencipta tatasusunan untuk julat.

Kita boleh mempunyai penyelesaian yang lebih cekap (bijak storan) menggunakan manipulasi bit.
Malah, kami boleh menggunakan operasi XOR untuk membantu kami dengan itu.

Untuk diingati, XOR menghasilkan 1 jika kedua-dua bit adalah berbeza — iaitu, satu daripadanya ialah 0 dan yang lain ialah 1.
Apabila kita XOR nombor dengan dirinya sendiri, ia akan menghasilkan 0, kerana semua bit adalah sama.

Sebagai contoh, 3 dalam binari ialah 11, apabila kita lakukan 11 ^ 11 hasilnya ialah 0:

const n = 3;
const result = n ^ n; // 0

Dalam erti kata lain, operasi XOR bagi nombor dengan dirinya sendiri akan menghasilkan 0.

Jika kita melakukan XOR dengan setiap nombor dalam tatasusunan dengan indeks, akhirnya kesemuanya akan dibatalkan (menghasilkan 0), hanya meninggalkan nombor yang hilang.

Anda mungkin berfikir bahawa tidak semua nombor berada pada indeksnya, contohnya jika nombor ialah [3, 0, 1], jelas sekali 3 tidak mempunyai "indeks 3" yang boleh dikaitkan dengannya!

Untuk itu, kita boleh mulakan dengan memulakan hasil kita kepada nums.length. Sekarang, walaupun nombor yang hilang adalah sama dengan nums.length, kami mengendalikan kes tepi itu.

let result = nums.length;

Selain itu, XOR ialah komutatif dan bersekutu, jadi tidak penting pada indeks mana nombor muncul (atau tidak mempunyai satu, seperti dalam contoh di atas) — akhirnya nombor itu akan dibatalkan.

Kini, dengan gelung for, kita boleh melakukan XOR menggunakan pengendali tugasan XOR bitwise:

for (let i = 0; i < nums.length; i++) {
  result ^= i ^ nums[i];
}

Dan, keputusan akhir ialah nombor yang hilang. Penyelesaian keseluruhannya kelihatan seperti ini:

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

Kerumitan masa dan ruang

Kerumitan masa sekali lagi $O(n)$O(n) seperti yang kita lelaran melalui setiap nombor dalam tatasusunan, tetapi kerumitan ruang akan menjadi $O(1)$O(1) kerana kami tidak mempunyai sebarang keperluan storan tambahan yang akan berkembang apabila saiz input meningkat.

---

Seterusnya, kita akan melihat masalah akhir keseluruhan siri, Jumlah Dua Integer. Sehingga itu, selamat mengekod.

Atas ialah kandungan terperinci Meditasi LeetCode: Nombor Hilang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!