Contains Duplicate

Q: Berapa kompleksitas waktu dari Contains Duplicate?

Solusi hash set berjalan dalam waktu rata-rata O(n) dan menggunakan ruang tambahan O(n) . Mengurutkan terlebih dahulu membutuhkan waktu O(n log n) dan tidak memerlukan array tambahan jika kamu boleh mengurutkan ulang input. Membandingkan setiap pasangan membutuhkan waktu O(n²) .

Q: Apakah membandingkan ukuran set dengan panjang array merupakan solusi yang valid?

Ya. Buat set dari seluruh nums dan periksa apakah ukurannya lebih kecil daripada array. Proses ini berjalan dalam waktu O(n) dan menggunakan ruang O(n) .

MudahHashing

+10

Kamu mendapatkan sebuah array bilangan bulat nums. Kembalikan true jika ada nilai yang muncul setidaknya dua kali, dan false jika semua nilainya berbeda.

Fungsi

containsDuplicate(nums: integer-array) → boolean

numsinteger-array: bilangan bulat yang akan diperiksa
Mengembalikanboolean: true jika suatu nilai muncul setidaknya dua kali, false jika tidak

Batasan

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Contoh

Input: nums = [3, 1, 4, 1, 5]
Output: true
Penjelasan: Nilai 1 muncul pada indeks 1 dan muncul lagi pada indeks 3, jadi jawabannya adalah true.

Input: nums = [2, 7, 1, 8]
Output: false
Penjelasan: 2, 7, 1, dan 8 adalah empat nilai yang berbeda, jadi tidak ada yang berulang.

Input: nums = [-4, 4, 0]
Output: false
Penjelasan: -4 dan 4 memiliki nilai absolut yang sama, tetapi merupakan angka yang berbeda, dan 0 muncul satu kali, jadi jawabannya adalah false.

Pertanyaan lanjutan

Bisakah kamu berhenti begitu menemukan nilai pertama yang berulang, alih-alih selalu membaca seluruh array?

Petunjuk

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

0 dari 3 dibuka

Solusi

Pengulangan adalah nilai yang pernah kamu temui sebelumnya, jadi tantangannya adalah menjawab pertanyaan "apakah aku pernah menemui ini?" dengan cepat. Membandingkan setiap pasangan memerlukan sekitar 5 × 10^7 perbandingan untuk n = 10^4. Pengurutan menempatkan nilai yang sama berdampingan, dan hash set menjawab pertanyaan tersebut dalam O(1) secara rata-rata, sehingga cukup dengan satu kali lintasan.

Urutkan, lalu bandingkan elemen yang bersebelahan

Intuisi

Dalam array yang sudah diurutkan, nilai yang sama akan bersebelahan: [3, 1, 4, 1, 5] diurutkan menjadi [1, 1, 3, 4, 5], dan kedua 1 itu berdampingan. Jadi, setelah mengurutkan, kamu hanya perlu membandingkan setiap nilai dengan nilai sebelumnya, sebanyak n-1 perbandingan.

Jika tidak ada dua tetangga yang nilainya sama, berarti tidak ada dua nilai yang sama di mana pun: nilai apa pun di antara dua salinan x dalam urutan terurut akan bernilai setidaknya x dan paling banyak x, jadi nilai itu pasti x juga.

Pengurutan membutuhkan waktu O(n log n), yang mendominasi. Mengurutkan langsung di tempat tidak membutuhkan array tambahan, tetapi mengubah urutan input milik pemanggil; mengurutkan salinan membutuhkan ruang O(n).

Algoritma

Urutkan nums secara menaik.
Lakukan perulangan pada i dari 1 hingga indeks terakhir.
Jika nums[i] sama dengan nums[i-1], kembalikan true.
Setelah perulangan, kembalikan false.

def containsDuplicate(nums):
    nums.sort()
    # After sorting, equal values sit next to each other.
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Satu kali pemindaian dengan hash set

Intuisi

Telusuri array satu kali dan simpan setiap nilai yang sudah kamu lewati dalam set hash. Set selalu berisi tepat nilai-nilai sebelum posisi saat ini, jadi kecocokan berarti nilai saat ini muncul sebelumnya, dan jika mencapai akhir tanpa kecocokan, berarti semua nilainya berbeda. Untuk [3, 1, 4, 1, 5], set berisi {3, 1, 4} saat 1 yang kedua ditemukan.

Pencarian dan penyisipan rata-rata membutuhkan waktu O(1), jadi proses ini membutuhkan waktu O(n). Jika tidak ada nilai berulang, set akan berisi semua n nilai.

Algoritma

Buat hash set kosong seen.
Untuk setiap nilai di nums, jika nilai tersebut ada di seen, kembalikan true.
Jika tidak, tambahkan nilai tersebut ke seen.
Setelah perulangan, kembalikan false.

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Jebakan dan kasus tepi

Memulai perulangan bagian dalam untuk pemeriksaan pasangan pada j = i. Setiap nilai kemudian cocok dengan dirinya sendiri dan jawabannya selalu true.
Membandingkan nilai yang bersebelahan tanpa mengurutkannya terlebih dahulu. Dalam [9, 1, 2, 3, 9], kedua 9 tidak bersebelahan.
Memulai perulangan untuk nilai yang bersebelahan pada indeks 0 dan membaca nums[-1]. Mulai dari 1, dan array dengan satu nilai akan mengembalikan false dengan benar.
Menganggap nilai dengan nilai absolut yang sama sebagai nilai yang sama, misalnya dengan melakukan hashing pada abs(x). -4 dan 4 adalah angka yang berbeda.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Contains Duplicate?

Solusi hash set berjalan dalam waktu rata-rata O(n) dan menggunakan ruang tambahan O(n). Mengurutkan terlebih dahulu membutuhkan waktu O(n log n) dan tidak memerlukan array tambahan jika kamu boleh mengurutkan ulang input. Membandingkan setiap pasangan membutuhkan waktu O(n²).

Bisakah kamu menyelesaikan Contains Duplicate tanpa ruang tambahan?

Ya, jika array boleh kamu susun ulang: urutkan langsung dan bandingkan setiap nilai dengan nilai di sebelahnya, menukar set O(n) dengan waktu O(n log n). Tanpa menyusun ulang dan tanpa memori tambahan, satu-satunya pilihan yang tersisa adalah pemeriksaan pasangan O(n²).

Apakah membandingkan ukuran set dengan panjang array merupakan solusi yang valid?

Ya. Buat set dari seluruh nums dan periksa apakah ukurannya lebih kecil daripada array. Proses ini berjalan dalam waktu O(n) dan menggunakan ruang O(n).

def containsDuplicate(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 1, 4, 1, 5]

Output yang diharapkan

true