Intersection of Two Arrays
Kamu mendapatkan dua array bilangan bulat, nums1 dan nums2. Kembalikan setiap nilai yang muncul di kedua array, diurutkan dari yang terkecil ke yang terbesar. Setiap nilai yang sama muncul satu kali dalam jawaban, sebanyak apa pun nilai itu berulang di salah satu array.
Fungsi
- nums1integer-array
- daftar bilangan bulat pertama
- nums2integer-array
- daftar bilangan bulat kedua
- Mengembalikaninteger-array
- nilai yang terdapat di kedua list, masing-masing satu kali, dalam urutan menaik
Batasan
1 ≤ nums1.length, nums2.length ≤ 5000-105 ≤ nums1[i], nums2[i] ≤ 105- Setidaknya satu nilai muncul di kedua array.
Contoh
- Input
- nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
- Output
- [4, 6]
- Penjelasan
4dan6ada di kedua array.4muncul dua kali dinums2, tetapi hanya dicantumkan sekali, sedangkan2dan9tidak pernah muncul dinums2.
- Input
- nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
- Output
- [-3, 7]
- Penjelasan
-3dan7ada di kedua array. Dalam urutan menaik,-3berada lebih dulu, meskipun7berada lebih dulu dinums2.
Pertanyaan lanjutan
Bagaimana jika nums1 berisi 10 nilai dan nums2 berisi satu juta nilai yang sudah diurutkan? Pendekatan mana yang akan kamu pilih, dan apakah pencarian biner bisa lebih cepat daripada menelusuri semuanya?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Untuk setiap nilai
nums1, kamu bisa memindai seluruh isinums2. Dengan 5000 nilai di setiap array, jumlahnya bisa mencapai2.5 × 10^7perbandingan. Pertanyaan apa yang kamu ajukan berulang kali?Pertanyaan yang berulang adalah "apakah nilai ini ada di array lainnya?". Hash set yang dibuat dari salah satu array menjawabnya dalam waktu konstan secara rata-rata.
Buat set dari
nums1. Telusurinums2; saat suatu nilai ada di dalam set, tambahkan ke jawaban dan hapus dari set, sehingga salinan berikutnya tidak dapat ditambahkan lagi. Urutkan jawaban sebelum mengembalikannya.
Solusi
Setiap nilai yang sama dimasukkan ke dalam jawaban satu kali, berapa pun jumlah kemunculannya, dan jawaban harus diurutkan. Mengurutkan kedua array memungkinkan dua pointer menemukan nilai yang sama secara berurutan, dan hash set dari salah satu array menjawab pertanyaan "apakah nilai ini ada di nums1?" dalam waktu konstan.
Bandingkan setiap pasangan
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Untuk setiap nilai nums1, telusuri nums2 dan berhenti pada kecocokan pertama. Lewati nilai yang sudah ada dalam jawaban, jadi [8, 8, 8, 8] dibandingkan dengan [8, 8] menghasilkan satu 8, lalu urutkan jawaban di akhir. Sebuah nilai dimasukkan tepat ketika salah satu kemunculannya menemukan kecocokan, dan langkah melewati nilai yang sudah ada membuatnya hanya muncul sekali. Setiap nilai mungkin menelusuri seluruh nums2: dengan 5000 nilai di setiap array, jumlahnya bisa mencapai 2.5 × 10^7 perbandingan, dan ketika hanya sedikit nilai yang cocok, sebagian besar penelusuran berlanjut hingga akhir.
Algoritma
- Mulai dengan list jawaban kosong.
- Untuk setiap nilai
adinums1, lewati jika sudah ada di jawaban. - Jika tidak, telusuri
nums2; saat menemukan nilai pertama yang sama dengana, tambahkanake jawaban dan hentikan penelusuran. - Urutkan jawaban dari nilai terkecil ke terbesar, lalu kembalikan.
def intersection(nums1, nums2):
result = []
for a in nums1:
if a in result:
continue
# Look for a anywhere in nums2.
for b in nums2:
if a == b:
result.append(a)
break
result.sort()
return resultUrutkan keduanya, lalu telusuri dengan dua pointer
Intuisi
Setelah diurutkan, contoh 1 menjadi [2, 2, 4, 6, 9] dan [1, 4, 4, 6]. Pindahkan pointer pada nilai yang lebih kecil: nilai itu tidak mungkin cocok dengan nilai apa pun yang ada lebih jauh di array lainnya, karena setiap nilainya setidaknya sama besar. Nilai yang sama muncul di kedua array, jadi tambahkan nilainya dan pindahkan kedua pointer. Nilai yang berulang di kedua sisi, seperti 2 dalam [2, 2, 3] dan [2, 2], cocok dua kali; bandingkan dengan nilai terakhir yang ditambahkan agar hanya satu salinan yang tersimpan. Hasilnya terurut.
Pengurutan membutuhkan O(n log n + m log m) dan proses penelusuran membutuhkan O(n + m), karena setiap langkah memindahkan satu pointer. Mengurutkan salinan membutuhkan memori O(n + m); pengurutan di tempat, seperti yang dilakukan kode C, hanya menyisakan hasilnya.
Algoritma
- Urutkan kedua array.
- Tetapkan
i = 0danj = 0. - Selama kedua pointer berada di dalam array masing-masing, pindahkan pointer yang menunjuk ke nilai lebih kecil.
- Jika nilainya sama, tambahkan nilai itu kecuali jika sama dengan nilai terakhir yang ditambahkan, lalu pindahkan kedua pointer.
- Kembalikan jawabannya.
def intersection(nums1, nums2):
a = sorted(nums1)
b = sorted(nums2)
i, j = 0, 0
result = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
# A shared value: keep it once, even if it repeats.
if not result or result[-1] != a[i]:
result.append(a[i])
i += 1
j += 1
return resultHash set dari array pertama
Intuisi
Masukkan setiap nilai dari nums1 ke dalam hash set. Pada contoh 1, 2 yang berulang dilebur, sehingga tersisa {6, 2, 9, 4}. Telusuri nums2 dan cari setiap nilai dalam waktu konstan, lalu hapus nilai dari set saat cocok: 4 yang pertama masuk ke dalam jawaban, sedangkan yang kedua tidak menemukan apa pun. Setiap nilai yang ditambahkan ada di kedua array, dan setiap nilai yang sama ditambahkan pada kemunculan pertamanya di nums2.
Penelusuran membutuhkan waktu rata-rata O(n + m). Jawaban mengikuti urutan nums2, jadi urutkan k ≤ min(n, m) nilainya dalam O(k log k). C tidak memiliki set bawaan, jadi kode C menggunakan array penanda dengan indeks value + 10^5.
Algoritma
- Buat hash set
firstdarinums1. - Untuk setiap nilai di
nums2, jika nilai tersebut ada difirst, tambahkan ke jawaban dan hapus darifirst. - Urutkan jawaban dari nilai terkecil ke terbesar.
- Kembalikan jawaban.
def intersection(nums1, nums2):
first = set(nums1)
result = []
for num in nums2:
if num in first:
result.append(num)
# Remove it so a repeat in nums2 is not added twice.
first.remove(num)
result.sort()
return result
Jebakan dan kasus tepi
- Menambahkan nilai setiap kali nilainya cocok.
[2, 2, 3, 3, 3]dan[3, 2, 2]menghasilkan[2, 3], bukan[3, 2, 2]. - Mengembalikan nilai dalam urutan saat kamu menemukannya. Penelusuran hash set mengikuti
nums2, jadi[7, -3]harus diurutkan menjadi[-3, 7].set(nums1) & set(nums2)di Python juga memerlukansorted. - Mengurutkan angka sebagai teks.
sort()di JavaScript tanpa pembanding mempertahankan urutan[100000, 99]. Berikan(x, y) => x - y. - Mengindeks array penanda menggunakan nilai mentah.
-3bukan indeks yang valid; geser setiap nilai sebesar10^5.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu dari irisan dua array?
Dengan hash set, menemukan nilai yang sama memerlukan waktu rata-rata O(n + m), ditambah O(k log k) untuk mengurutkan jawaban, dan ruang O(n). Mengurutkan kedua array lalu menelusurinya memerlukan waktu O(n log n + m log m). Membandingkan setiap pasangan memerlukan waktu O(n × m).
Haruskah kamu menggunakan hash set atau dua pointer?
Gunakan hash set saat array belum diurutkan dan memori tersedia: cara ini membutuhkan pekerjaan paling sedikit. Gunakan dua pointer saat kedua array sudah diurutkan, atau saat memori terbatas dan kamu boleh mengurutkannya di tempat. Penelusuran ini tidak memerlukan set dan menghasilkan jawaban secara berurutan.
Bagaimana cara menyimpan nilai yang berulang dalam irisan?
Jika sebuah nilai harus muncul sebanyak kemunculannya di kedua array, sehingga [3, 1, 3, 3] dan [3, 3] menghasilkan [3, 3], hitung nums1 dalam sebuah map. Untuk setiap nilai nums2 yang jumlahnya lebih dari nol, tambahkan nilai itu dan kurangi jumlahnya. Penelusuran dua pointer hanya menghapus pemeriksaannya terhadap nilai terakhir yang ditambahkan.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def intersection(nums1, nums2):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
nums1 = [6, 2, 9, 2, 4] nums2 = [4, 4, 1, 6]
Output yang diharapkan
[4, 6]