Remove Duplicates from Sorted Array

+10

Kamu mendapatkan array bilangan bulat nums yang diurutkan dalam urutan tidak menurun, sehingga nilai yang sama berada berdampingan. Kembalikan nilai-nilai berbeda dari nums, masing-masing satu kali, sesuai urutan kemunculannya. Contohnya, [2, 2, 5] menghasilkan [2, 5].

Fungsi

removeDuplicates(nums: integer-array) → integer-array

numsinteger-array: bilangan bulat, diurutkan secara tidak menurun
Mengembalikaninteger-array: nilai-nilai berbeda dari nums, dalam urutan menaik

Batasan

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums diurutkan dalam urutan tidak menurun.

Contoh

Input: nums = [1, 1, 2, 3, 3, 3]
Output: [1, 2, 3]
Penjelasan: 1 muncul dua kali dan 3 muncul tiga kali. Menyisakan satu dari masing-masing menghasilkan [1, 2, 3].

Input: nums = [-2, 0, 0, 5]
Output: [-2, 0, 5]
Penjelasan: Hanya 0 yang berulang. Nilai negatif bekerja dengan cara yang sama, jadi jawabannya adalah [-2, 0, 5].

Input: nums = [7, 7, 7]
Output: [7]
Penjelasan: Setiap nilai adalah 7, jadi hanya satu 7 yang tersisa.

Pertanyaan lanjutan

Bisakah kamu melakukannya dengan memori tambahan O(1), dengan menulis ulang nums langsung alih-alih membuat array kedua?

Petunjuk

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

0 dari 3 dibuka

Solusi

Dalam array yang tidak terurut, kamu harus mengingat setiap nilai yang sudah dilihat. Pengurutan menempatkan semua salinan suatu nilai secara berurutan, sehingga suatu nilai dianggap baru tepat ketika berbeda dari nilai terakhir yang kamu simpan. Satu kali lintasan dengan indeks baca dan indeks tulis menyelesaikan pekerjaan ini langsung di tempat.

Ingat nilai yang sudah dilihat dalam hash set

Intuisi

Telusuri nums dan simpan nilai yang sudah ada dalam jawaban di sebuah set. Tambahkan nilai saat pertama kali kamu menemukannya dan lewati setelah itu, sehingga setiap nilai muncul sekali, sesuai urutan kamu menemukannya. Cara ini tidak menggunakan urutan pengurutan dan berfungsi pada array apa pun.

Pencarian dalam set rata-rata memerlukan waktu O(1), jadi proses ini memerlukan waktu O(n), tetapi set dan jawaban masing-masing dapat menampung n nilai: ruang ekstra O(n). Dalam C, array berisi penanda untuk 2 × 10^4 + 1 kemungkinan nilai menggantikan set.

Algoritma

Buat set kosong seen dan list kosong result.
Untuk setiap nilai di nums, periksa apakah nilai tersebut ada di seen.
Jika tidak, tambahkan nilai tersebut ke seen dan tambahkan ke result.
Kembalikan result.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

Padatkan langsung di tempat dengan pointer penulisan

Intuisi

Indeks tulis k menandai akhir bagian yang dipertahankan: nums[0] hingga nums[k-1] selalu berisi nilai-nilai berbeda yang ditemukan sejauh ini, sehingga nums[k-1] adalah nilai terakhir yang dipertahankan. Indeks baca i mengunjungi setiap nilai. Nilai yang sama dengan nums[k-1] adalah salinan lain dari deretan yang sudah kamu pertahankan; nilai yang berbeda memulai deretan baru dan ditempatkan di nums[k].

Pada [1, 1, 2, 3, 3, 3], i = 1 melewati angka 1 yang kedua, i = 2 menulis 2 ke indeks 1, i = 3 menulis 3 ke indeks 2, dan dua angka 3 terakhir dilewati. Tiga slot pertama berisi [1, 2, 3].

Karena k tidak pernah melewati i, penulisan tidak pernah menimpa nilai yang belum kamu baca. Proses ini membutuhkan waktu O(n) dan ruang tambahan sebesar dua bilangan bulat.

Algoritma

Tetapkan k = 1: nums[0] selalu dipertahankan.
Ulangi i dari 1 hingga indeks terakhir.
Jika nums[i] berbeda dari nums[k-1], tetapkan nums[k] = nums[i] dan tambahkan 1 ke k.
Kembalikan k nilai pertama dari nums.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

Jebakan dan kasus tepi

Membandingkan nums[i] dengan nums[i+1] saat i berjalan hingga indeks terakhir. Perbandingan terakhir membaca satu posisi melewati akhir.
Memulai k dari 0. Nilai pertama kemudian dibandingkan dengan nums[-1], yang berada di luar rentang atau, dalam Python, merupakan elemen terakhir.
Mengembalikan seluruh array, bukan k nilai pertamanya. Bagian akhir masih menyimpan nilai lama, jadi [1, 1, 2] menjadi [1, 2, 2].
Menyusun jawaban dengan melakukan iterasi pada hash set. Sebagian besar hash set tidak menyimpan urutan, jadi nilai-nilainya bisa keluar dalam urutan acak.
Dalam Lua dan R, array dimulai dari 1. Bagian yang dipertahankan adalah nums[1] hingga nums[k], dan kamu membandingkannya dengan nums[k].

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Remove Duplicates from Sorted Array?

Solusi dengan pointer tulis membaca setiap nilai satu kali, sehingga berjalan dalam waktu O(n). Selain nilai yang dikembalikannya, solusi ini menggunakan ruang tambahan O(1): dua indeks.

Mengapa array perlu diurutkan?

Pengurutan menempatkan setiap salinan nilai dalam satu rangkaian, jadi membandingkannya dengan nilai terakhir yang dipertahankan sudah cukup. Dalam array yang tidak terurut, salinan bisa muncul di mana saja, jadi kamu memerlukan hash set yang berisi setiap nilai yang telah ditemukan, yang membutuhkan ruang tambahan O(n).

Bagaimana kamu mengizinkan setiap nilai muncul paling banyak dua kali?

Bandingkan dengan nilai dua posisi sebelumnya di bagian yang dipertahankan, bukan satu: salin nums[i] jika k < 2 atau jika nilainya berbeda dari nums[k-2]. Jika nilainya sama dengan nums[k-2], bagian yang dipertahankan sudah diakhiri dengan dua salinannya. Gagasan yang sama memungkinkan paling banyak m salinan dengan nums[k-m].

def removeDuplicates(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [1, 1, 2, 3, 3, 3]

Output yang diharapkan

[1, 2, 3]