Single Number
Kamu mendapatkan sebuah list nums yang setiap nilainya muncul tepat dua kali, kecuali satu nilai yang hanya muncul sekali. Kembalikan nilai yang muncul sekali.
Fungsi
- numsinteger-array
- sebuah list yang setiap nilainya muncul dua kali, kecuali satu nilai
- Mengembalikaninteger
- nilai yang hanya muncul satu kali
Batasan
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Setiap nilai muncul tepat dua kali, kecuali satu nilai yang muncul tepat satu kali.
Contoh
- Input
- nums = [8, 3, 8]
- Output
- 3
- Penjelasan
- 8 muncul dua kali dan 3 muncul satu kali, jadi jawabannya adalah 3.
- Input
- nums = [5, -2, 7, 5, 7]
- Output
- -2
- Penjelasan
- 5 dan 7 masing-masing muncul dua kali, dan -2 adalah satu-satunya nilai yang muncul sekali.
- Input
- nums = [42]
- Output
- 42
- Penjelasan
- List dengan satu nilai sama sekali tidak memiliki pasangan, jadi nilai itu adalah jawabannya.
Pertanyaan lanjutan
Bagaimana jika setiap nilai muncul tiga kali kecuali satu nilai? XOR saja tidak lagi membatalkan nilai-nilai yang muncul tiga kali. Bisakah kamu tetap menemukan satu nilai tersebut dalam waktu O(n) dan menggunakan memori tambahan O(1)?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Jika setiap pasangan nilai yang sama bisa dihilangkan, hanya jawabannya yang tersisa. Apakah ada operasi yang mengubah dua angka yang sama menjadi ketiadaan?
XOR bekerja seperti ini:
x ^ xadalah0danx ^ 0adalahx. XOR juga tidak bergantung pada urutan, jadi dua salinan nilai tidak harus bersebelahan untuk saling menghapus.Simpan satu variabel yang dimulai dari
0. Lakukan XOR pada setiap nilai dinumsdengannya, lalu kembalikan nilainya. Tidak perlu menggunakan map atau mengurutkan.
Solusi
Hash map menemukan nilai yang tidak memiliki pasangan dengan menghitung, tetapi map bertambah seiring dengan list. XOR tidak memerlukan penghitungan, karena nilai yang di-XOR dengan dirinya sendiri menghasilkan 0. Lakukan XOR pada seluruh list sekaligus, dan setiap pasangan akan saling menghapus, sehingga menyisakan satu nilai dalam satu variabel.
Hitung setiap nilai dengan memindai
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Untuk setiap nilai, telusuri seluruh list dan hitung kemunculannya. Kembalikan nilai pertama yang jumlah kemunculannya 1. Jumlah kemunculan mengikuti definisi jawaban, jadi hasilnya benar. Setiap dari n nilai memicu penelusuran terhadap n nilai, sehingga ada hampir 10^8 perbandingan saat nilai tunggal berada di akhir list yang berisi 9,999 nilai.
Algoritma
- Lakukan perulangan pada setiap nilai dalam
nums. - Pindai seluruh list dan hitung nilai yang sama dengannya.
- Jika hitungannya 1, kembalikan nilai tersebut.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Menghitung dengan hash map
Intuisi
Hitung setiap nilai dalam satu kali lintasan menggunakan hash map yang memetakan nilai ke jumlahnya. Untuk [5, -2, 7, 5, 7], hasil akhirnya di map adalah 5 → 2, -2 → 1, 7 → 2, dan satu lintasan pada map menemukan -2.
Setiap nilai memerlukan satu pembaruan map, jadi waktunya O(n). Map menyimpan sekitar n/2 entri, dengan memori tambahan O(n). C tidak memiliki map bawaan, jadi array penghitung yang diindeks dengan value + 10^4 berperan sebagai penggantinya.
Algoritma
- Buat map kosong dari nilai ke jumlah.
- Untuk setiap nilai dalam
nums, tambahkan 1 ke jumlahnya. - Telusuri map dan kembalikan nilai yang jumlahnya 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0Lakukan XOR pada semua nilai
Intuisi
XOR menetapkan bit saat kedua inputnya berbeda. Jadi x ^ x = 0, x ^ 0 = x, dan urutan operasinya tidak penting.
Lakukan XOR pada seluruh list ke dalam variabel yang dimulai dari 0. Kelompokkan ulang operasinya agar setiap nilai bertemu pasangannya: setiap pasangan menjadi 0, dan 0 ^ single menyisakan nilai tunggal. Untuk [8, 3, 8]: 0 ^ 8 = 8, lalu 8 ^ 3 = 11, lalu 11 ^ 8 = 3. Perulangan membaca setiap nilai satu kali dan menyimpan satu variabel: waktu O(n) dan memori tambahan O(1).
Algoritma
- Tetapkan
resultke 0. - Untuk setiap nilai dalam
nums, tetapkanresultkeresult ^ value. - Kembalikan
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Jebakan dan kasus tepi
- Memulai
resultdengannums[0], lalu melakukan perulangan pada setiap nilai, termasuk indeks 0. Nilai pertama dioperasikan dengan XOR dua kali dan saling membatalkan. Mulai dari 0, atau lewati indeks 0. - Mengurutkan dan membandingkan nilai-nilai yang bersebelahan dalam langkah dua, lalu lupa bahwa satu nilai bisa berada di posisi terakhir. Dalam
[1, 1, 2], setiap pasangan yang diperiksa cocok, dan jawabannya adalah nilai 2 yang tersisa. - Menggunakan kembali perulangan XOR saat nilai bisa muncul dalam jumlah ganjil. Operasi ini hanya membatalkan jumlah kemunculan genap, jadi dalam
[4, 4, 4, 9], hasilnya4 ^ 9 = 13, bukan 9.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu Single Number?
Solusi XOR berjalan dalam waktu O(n) dan menggunakan ruang tambahan O(1). Hash map juga membutuhkan waktu O(n), tetapi memerlukan memori O(n). Menghitung setiap nilai dengan pemindaian baru membutuhkan waktu O(n²).
Apakah solusi XOR berfungsi dengan bilangan negatif?
Ya. XOR bekerja pada bit yang menyimpan angka, dan angka negatif disimpan dalam bentuk komplemen dua. Dua angka negatif yang sama memiliki bit identik, sehingga keduanya saling meniadakan persis seperti angka positif. Dalam [5, -2, 7, 5, 7], hasilnya adalah -2.
Bisakah kamu menyelesaikan Single Number dengan penjumlahan alih-alih XOR?
Ya. 2 × sum(distinct values) - sum(nums) adalah nilai tunggalnya: setiap nilai berpasangan dijumlahkan dua kali di kedua sisi, sedangkan nilai tunggal dijumlahkan dua kali di satu sisi dan sekali di sisi lainnya. Untuk [5, -2, 7, 5, 7], hasilnya 2 × 10 - 22 = -2. Set nilai yang berbeda memerlukan memori sebesar O(n), yang dapat dihindari dengan XOR.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def singleNumber(nums):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [8, 3, 8]
Output yang diharapkan
3