Missing Number

Q: Berapa kompleksitas waktu dari Missing Number?

Solusi penjumlahan dan XOR sama-sama berjalan dalam waktu O(n) dengan ruang ekstra O(1) : keduanya membaca setiap nilai satu kali dan menyimpan satu angka. Mencari setiap kandidat di dalam list membutuhkan O(n²) , sedangkan mengurutkan terlebih dahulu untuk menemukan celah membutuhkan O(n log n) .

Q: Bisakah kamu menyelesaikan Missing Number dengan hash set?

Ya. Masukkan setiap nilai ke dalam set, lalu periksa 0 hingga n dan kembalikan angka pertama yang tidak ada di dalam set. Cara ini berjalan dalam waktu O(n) , tetapi menggunakan memori tambahan O(n) , yang dihindari oleh metode penjumlahan dan XOR.

MudahManipulasi bit Matematika dan simulasi

+10

Kamu mendapatkan list nums yang berisi n bilangan bulat berbeda, masing-masing antara 0 dan n. Rentang dari 0 hingga n memuat n+1 bilangan, jadi tepat satu bilangan tidak ada di dalam list. Kembalikan bilangan yang hilang tersebut.

Fungsi

missingNumber(nums: integer-array) → integer

numsinteger-array: n bilangan bulat berbeda dari rentang 0 hingga n, dalam urutan apa pun
Mengembalikaninteger: satu angka dari 0 sampai n yang tidak ada di nums

Batasan

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
Semua nilai dalam nums berbeda.

Contoh

Input: nums = [4, 2, 0, 1]
Output: 3
Penjelasan: list ini memiliki 4 nilai, jadi rentangnya dari 0 sampai 4. list ini berisi 0, 1, 2, dan 4, sedangkan 3 adalah satu-satunya angka yang tidak memiliki pasangan.

Pertanyaan lanjutan

Jika list sudah terurut, bisakah kamu menemukan angka yang hilang dalam waktu O(log n) dengan pencarian biner?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Kamu tahu isi list yang seharusnya: setiap bilangan bulat dari 0 hingga n. Ringkas rentang penuh dan list menjadi satu nilai ringkasan masing-masing, yaitu jumlah atau XOR, dan selisih antara keduanya adalah angka yang hilang. Cara ini hanya membutuhkan satu kali penelusuran dan tidak membutuhkan memori tambahan.

Periksa setiap kandidat

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Periksa kandidat 0 sampai n secara berurutan dan telusuri list untuk setiap kandidat. Setiap angka dalam rentang tersebut ada di dalam list atau merupakan jawabannya, jadi kandidat pertama yang tidak ditemukan adalah angka yang hilang.

Setiap kandidat memerlukan pemindaian hingga n nilai. Dengan n = 10^4 dan celahnya berada di dekat angka teratas, jumlahnya sekitar 5 × 10^7 perbandingan.

Algoritma

Ulangi candidate dari 0 hingga n, termasuk n.
Pindai nums untuk mencari nilai yang sama dengan candidate.
Jika pemindaian menemukannya, lanjutkan ke kandidat berikutnya.
Jika pemindaian berakhir tanpa kecocokan, kembalikan candidate.

def missingNumber(nums):
    n = len(nums)
    for candidate in range(n + 1):
        # "in" on a list scans it from the start: O(n) per candidate.
        if candidate not in nums:
            return candidate
    return -1

Kurangi jumlah tersebut dari jumlah yang diharapkan

Intuisi

Jumlah angka 0 sampai n adalah n(n+1)/2. list tersebut berisi semua angka itu kecuali satu angka, jadi jumlahnya kurang tepat sebesar angka tersebut. Untuk [4, 2, 0, 1], jumlah rentangnya adalah 4 × 5 / 2 = 10 dan jumlah list adalah 7, sehingga selisihnya 3.

Satu kali penelusuran menjumlahkan seluruh isi list: waktu O(n) dan satu total berjalan.

Algoritma

Misalkan n adalah panjang nums.
Hitung jumlah total n(n+1)/2.
Jumlahkan semua nilai dalam nums.
Kembalikan jumlah total dikurangi jumlah nilai dalam list.

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

XOR indeks dengan nilainya

Intuisi

XOR membatalkan pasangan: a ^ a adalah 0, a ^ 0 adalah a, dan urutannya tidak berpengaruh. Lakukan XOR pada indeks 0 hingga n bersama dengan nilainya. Sebuah angka dalam list muncul sekali sebagai indeks dan sekali sebagai nilai, jadi keduanya saling membatalkan. Angka yang hilang hanya muncul sebagai indeks, jadi angka itulah yang tersisa. Perulangan mengunjungi indeks 0 hingga n-1, jadi mulai hasilnya dari n.

Untuk [4, 2, 0, 1]: mulai dari 4, lalu lakukan XOR dengan 0 dan 4, 1 dan 2, 2 dan 0, 3 dan 1. Semua angka kecuali 3 muncul dua kali, jadi 3 yang tersisa. Nilai yang terus diperbarui tidak pernah menggunakan bit lebih banyak daripada n, jadi nilainya tidak bisa mengalami overflow.

Algoritma

Atur result ke n, panjang nums.
Untuk setiap indeks i, lakukan XOR pada result dengan i dan nums[i].
Kembalikan result.

def missingNumber(nums):
    # Start with n, the one index the loop below never reaches.
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

Jebakan dan kasus tepi

Lupa bahwa n sendiri bisa hilang. Dalam [0, 1, 2], jawabannya adalah 3, yang bukan indeks; versi XOR harus dimulai dari n.
Menggunakan ukuran rentang yang salah. Rentang 0 hingga n memuat n+1 angka, jadi jumlah totalnya adalah n(n+1)/2, bukan (n-1)n/2.
Memulai pencarian dari 1. Dalam [1], jawabannya adalah 0.
Terjadi overflow pada versi penjumlahan untuk input yang lebih besar. Dalam aritmetika 32-bit, n(n+1) mengalami overflow saat n melewati sekitar 46,000. Gunakan aritmetika 64-bit atau XOR.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Missing Number?

Solusi penjumlahan dan XOR sama-sama berjalan dalam waktu O(n) dengan ruang ekstra O(1): keduanya membaca setiap nilai satu kali dan menyimpan satu angka. Mencari setiap kandidat di dalam list membutuhkan O(n²), sedangkan mengurutkan terlebih dahulu untuk menemukan celah membutuhkan O(n log n).

Haruskah kamu menggunakan rumus penjumlahan atau XOR?

Keduanya memerlukan satu kali pemindaian dan memori konstan. Penjumlahan lebih mudah dijelaskan, tetapi hasil perkalian sementaranya memerlukan bilangan bulat 64-bit setelah n melewati sekitar 46.000. XOR tidak pernah mengalami overflow.

Bisakah kamu menyelesaikan Missing Number dengan hash set?

Ya. Masukkan setiap nilai ke dalam set, lalu periksa 0 hingga n dan kembalikan angka pertama yang tidak ada di dalam set. Cara ini berjalan dalam waktu O(n), tetapi menggunakan memori tambahan O(n), yang dihindari oleh metode penjumlahan dan XOR.

def missingNumber(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [4, 2, 0, 1]

Output yang diharapkan

Missing Number

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Periksa setiap kandidat

Kurangi jumlah tersebut dari jumlah yang diharapkan

XOR indeks dengan nilainya

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa