Find the Duplicate Number
Kamu mendapatkan array nums yang berisi n+1 bilangan bulat, masing-masing antara 1 dan n. Tepat satu nilai muncul lebih dari sekali, mungkin berkali-kali, dan kamu mengembalikan nilai tersebut.
Selesaikan tanpa mengubah nums dan hanya dengan menggunakan jumlah memori tambahan yang konstan.
Fungsi
- numsinteger-array
- n+1 bilangan bulat, masing-masing antara 1 dan n
- Mengembalikaninteger
- nilai yang muncul lebih dari sekali
Batasan
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- Tepat satu nilai muncul dua kali atau lebih; setiap nilai lainnya muncul paling banyak sekali.
Contoh
- Input
- nums = [2, 5, 1, 3, 5, 4]
- Output
- 5
- Penjelasan
- Di sini,
nbernilai 5, dan 5 berada di posisi 1 dan 4, jadi jawabannya adalah 5. Setiap nilai lainnya dari 1 hingga 5 muncul satu kali.
- Input
- nums = [4, 2, 4, 1, 4]
- Output
- 4
- Penjelasan
- 4 muncul tiga kali, pada posisi 0, 2, dan 4, sedangkan 3 tidak muncul sama sekali. Angka yang berulang dapat menggantikan beberapa nilai yang hilang, jadi jawabannya adalah 4.
Pertanyaan lanjutan
Pencarian biner pada nilai memenuhi kedua aturan dalam waktu O(n log n). Bisakah kamu mempertahankannya dalam waktu O(n)?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Setiap nilai berada di antara 1 dan
n, dan array memiliki posisi 0 hinggan. Jadi, setiap nilai juga merupakan posisi yang valid. Mulai dari posisi 0, lompat ke posisinums[0], lalu ke posisi yang disebutkan oleh nilai tersebut, dan seterusnya. Apa yang pasti terjadi pada penelusuran itu?Perjalanan ini tidak pernah berhenti dan hanya memiliki
n+1posisi untuk dikunjungi, sehingga termasuk perulangan. Posisi tempat perjalanan ini memasuki perulangan dicapai dari dua posisi berbeda, dan keduanya menyimpan posisi tersebut sebagai nilainya.Temukan titik masuk perulangan dengan dua pointer yang berangkat dari posisi 0: satu melompat sekali setiap putaran, yang lain dua kali, sampai keduanya mendarat di posisi yang sama. Lalu, kembalikan satu pointer ke posisi 0 dan gerakkan keduanya satu lompatan setiap kali. Keduanya akan bertemu di titik masuk, itulah jawabannya.
Solusi
hash set membutuhkan memori untuk setiap nilai, dan pengurutan mengubah nums. Setiap nilai berada di antara 1 dan n, jadi nilai itu juga merupakan posisi yang valid: baca nilai itu sebagai tautan. Penelusuran dari posisi 0 berakhir dalam perulangan yang titik masuknya adalah nilai duplikat, dan dua pointer Floyd menemukannya dalam O(n).
Bandingkan setiap pasangan
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Bandingkan setiap posisi dengan semua posisi setelahnya, lalu kembalikan nilai dari pasangan pertama yang sama. Tidak ada yang ditulis dan satu-satunya memori yang digunakan adalah dua penghitung, jadi kedua aturan terpenuhi. Dengan 10,001 nilai dan kedua salinannya berada dekat akhir, jumlahnya sekitar 5 × 10^7 pemeriksaan pasangan.
Algoritma
- Untuk setiap posisi
idari 0 hingga akhir: - Untuk setiap posisi
jsetelahi, bandingkannums[i]dengannums[j]. - Kembalikan
nums[i]saat kecocokan pertama ditemukan.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeatPencarian biner berdasarkan nilai
Intuisi
Telusuri rentang nilai, bukan posisinya. Untuk batas m, hitung entri yang nilainya paling banyak m. Jika nilai duplikat d lebih besar dari m, nilai 1 sampai m masing-masing muncul paling banyak sekali, jadi jumlahnya paling banyak m. Jika d paling banyak m, paling banyak n-m entri berada di atas m, jadi setidaknya m+1 entri bernilai paling banyak m. Tes "count > m" bernilai salah di bawah d dan benar mulai dari d, lalu pencarian biner menemukan m pertama yang membuatnya bernilai benar.
Dalam contoh kedua, m = 2 menghitung 2 dan 1, tidak lebih dari 2, dan m = 3 tetap menghitung 2, jadi jawabannya 4. Setiap putaran membaca array satu kali: sekitar 14 kali pemindaian terhadap 10,001 nilai.
Algoritma
- Tetapkan
low= 1 danhigh=n, panjangnumsdikurangi satu. - Selama
low < high, tentukanmiddi titik tengah antara keduanya. - Hitung entri
numsyang nilainya paling banyakmid. - Jika jumlahnya lebih besar dari
mid, tetapkanhigh=mid; jika tidak, tetapkanlow=mid+1. - Kembalikan
low.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return lowDeteksi siklus Floyd pada tautan nilai
Intuisi
Baca array sebagai tautan: posisi i menunjuk ke posisi nums[i]. Dengan n+1 posisi, masing-masing memiliki tautan, perjalanan dari 0 pasti mengunjungi kembali suatu posisi: ada ekor, lalu perulangan. Contoh pertama bergerak dari 0 ke 2, ke 1, lalu memutari 5 dan 4.
Pintu masuk perulangan dicapai dari dua posisi, satu di ekor dan satu di perulangan: di sini posisi 1 dan 4, yang keduanya berisi 5. Tidak ada nilai yang bernilai 0, jadi posisi 0 selalu berada di ekor dan pintu masuk selalu memiliki dua jalur masuk. Hanya satu nilai yang berulang, jadi pintu masuk adalah jawabannya.
Fase 1 menggerakkan slow satu tautan setiap putaran dan fast dua tautan hingga keduanya bertemu, setelah s putaran. Tambahan s langkah fast merupakan putaran penuh. Fase 2 memulai ulang slow dari 0. Setelah T langkah, yaitu panjang ekor, slow berada di pintu masuk, dan fast berada di posisi yang dicapai perjalanan dari 0 setelah T langkah ditambah putaran penuh: pintu masuk juga.
Algoritma
- Perlakukan setiap posisi
isebagai simpul yang terhubung ke posisinums[i], lalu mulai kedua pointer dari posisi 0. - Fase 1: pindahkan
slowkenums[slow]danfastkenums[nums[fast]]hingga keduanya sama. - Fase 2: atur kembali
slowke 0. - Pindahkan keduanya satu tautan setiap kali,
slowkenums[slow]danfastkenums[fast], hingga keduanya sama. - Kembalikan posisi tersebut: itulah nilai yang berulang.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Jebakan dan kasus tepi
- Mengembalikan titik pertemuan pada fase 1. Titik itu berada di suatu tempat dalam perulangan: pada contoh pertama, kedua pointer bertemu di 4, tetapi jawabannya adalah 5.
- Memeriksa
slow == fastsebelum langkah pertama. Keduanya mulai dari 0, jadi perulangan langsung berakhir. - Memulai penelusuran dari posisi selain 0. Posisi 3 pada contoh pertama terhubung ke dirinya sendiri, membentuk perulangan tanpa jalur masuk, jadi titik masuknya tidak membuktikan apa pun.
- Menguji
count >= middalam pencarian biner. Jika tidak ada nilai dari 1 hinggamyang berulang atau hilang, jumlahnya tepatm, jadi hanya>yang memisahkan kedua sisi. - Menandai nilai yang sudah terlihat dengan menegasikan entri atau menukar nilai ke tempatnya. Keduanya menemukan jawaban, tetapi keduanya mengubah array.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu untuk Find the Duplicate Number?
Deteksi siklus Floyd berjalan dalam waktu O(n) dengan memori tambahan O(1). Pencarian biner pada nilai membutuhkan waktu O(n log n) dan memori O(1), sedangkan membandingkan setiap pasangan membutuhkan waktu O(n²).
Mengapa tidak menggunakan hash set atau mengurutkan array?
Keduanya bisa digunakan dalam program nyata. Namun, tugas ini melarang keduanya: hash set menggunakan memori tambahan O(n), sedangkan pengurutan mengubah nums atau memerlukan salinan lengkap. Aturan inilah yang mengarahkanmu ke pendekatan siklus.
Mengapa rumus penjumlahan tidak berfungsi untuk Menemukan Angka Duplikat?
Mengurangkan 1 + 2 + ... + n dari jumlah array hanya menghasilkan nilai duplikat jika nilai itu muncul tepat dua kali. Di sini, nilai yang berulang dapat menggantikan nilai yang hilang: pada [4, 2, 4, 1, 4], selisihnya adalah 15 minus 10 = 5, nilai yang bahkan tidak ada di dalam array.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def findDuplicate(nums):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
nums = [2, 5, 1, 3, 5, 4]
Output yang diharapkan
5