Remove Duplicates from Sorted Array

Q: Ek bellek kullanmadan yinelenenleri yerinde nasıl kaldırırsınız?

Okuma indeksinin yanında bir yazma indeksi k tut. İlk k yuva, şimdiye kadar görülen farklı değerleri tutar. Okuduğun değer nums[k-1] değerinden farklı olduğunda, onu nums[k] konumuna kopyala ve k değerini ilerlet. Yazma indeksi hiçbir zaman okuma indeksini geçmez; böylece hiçbir şey okunmadan önce üzerine yazılmaz.

Kolayİki işaretçi

+10

Artan olmayan sırada sıralanmış bir tamsayı dizisi nums alırsın; bu nedenle eşit değerler yan yana bulunur. nums dizisindeki farklı değerleri, her birinden bir kez olacak şekilde ve göründükleri sırayla döndür. Örneğin, [2, 2, 5] sonucu [2, 5] olur.

Fonksiyon

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

numsinteger-array: azalmayan sırada sıralanmış tam sayılar
Döndürürinteger-array: nums dizisindeki farklı değerler, artan sırada

Kısıtlar

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums azalmayan sırada sıralanmıştır.

Örnekler

Girdi: nums = [1, 1, 2, 3, 3, 3]
Çıktı: [1, 2, 3]
Açıklama: 1 iki kez, 3 ise üç kez görünür. Her birinden bir tane bırakınca geriye [1, 2, 3] kalır.

Girdi: nums = [-2, 0, 0, 5]
Çıktı: [-2, 0, 5]
Açıklama: Yalnızca 0 tekrar eder. Negatif değerler de aynı şekilde çalışır, bu nedenle cevap [-2, 0, 5] olur.

Girdi: nums = [7, 7, 7]
Çıktı: [7]
Açıklama: Her değer 7, dolayısıyla geriye yalnızca bir 7 kalır.

Gönderirken +15 gizli test

Ek soru

Bunu, ikinci bir dizi oluşturmak yerine nums dizisini yerinde yeniden yazarak O(1) ek bellekle yapabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Keyfi bir diziden yinelenen öğeleri kaldırmak, gördüğünüz her değeri hatırlamak anlamına gelir. Sıralanmış girdi bu gereksinimi ortadan kaldırır: bir değerin kopyaları yan yana bulunur, dolayısıyla bir değer ancak tuttuğunuz son değerden farklıysa yenidir. Böylece işlem, iki indeksle ve ek bellek kullanmadan tek geçişte tamamlanır.

Görülen değerleri bir hash kümesinde hatırla

Sezgi

nums üzerinde ilerle ve yanıta daha önce eklediğin değerlerden oluşan bir küme tut. Bir değer kümede yoksa onu yanıta ekle ve kümeye dahil et; varsa atla. [1, 1, 2, 3, 3, 3] için yanıt önce [1], sonra [1, 2], ardından [1, 2, 3] olur ve sonraki her kopya atlanır.

Her değer, karşılaştığın sırayla ilk göründüğünde eklenir ve bir daha eklenmez; bu nedenle yanıt doğrudur. Bu yaklaşım, nums dizisinin sıralı olmasından yararlanmaz; herhangi bir dizi üzerinde çalışır.

Küme aramaları ortalama olarak O(1) sürdüğünden, geçiş O(n) zaman alır; ancak hem küme hem de yanıt n değer tutabilir: O(n) ek alan. C dilinde yerleşik bir küme olmadığından, olası 2 × 10^4 + 1 değer için bir bayrak dizisi aynı işi görür.

Algoritma

Boş bir seen kümesi ve boş bir result listesi oluştur.
nums içindeki her değer için, seen içinde olup olmadığını kontrol et.
İçinde değilse, onu seen kümesine ekle ve result listesine ekle.
result değerini döndür.

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

Yazma işaretçisiyle yerinde sıkıştırma

Sezgi

Sıralanmış girdide, bir değerin tüm kopyaları tek bir ardışık grup oluşturur; dolayısıyla bir değer, tuttuğun son değerden farklıysa yenidir. Bunun için bir küme değil, tek bir karşılaştırma gerekir.

İki indeks kullan. Okuma indeksi i her değeri ziyaret eder. Yazma indeksi k, tutulan kısmın sonunu işaretler: nums[0] ile nums[k-1] aralığı, şimdiye kadar bulunan farklı değerleri her zaman içerir. İlk değer her zaman tutulacağından k = 1 ile başla. nums[i], nums[k-1] değerinden farklı olduğunda, onu nums[k] konumuna kopyala ve k değerini ilerlet.

[1, 1, 2, 3, 3, 3] üzerinde: i = 1 ikinci 1 değerini okur ve hiçbir şey olmaz. i = 2, nums[0] = 1 değerinden farklı olan 2 değerini okur; bu nedenle 1. indekse yazılır ve k değeri 2 olur. i = 3, 3 değerini 2. indekse yazar ve k değeri 3 olur. Son iki 3, nums[2] ile eşleştiği için atlanır. İlk üç yuva artık [1, 2, 3] değerlerini içerir.

Yazma işlemi okuma işlemini hiçbir zaman geçmez; çünkü k her zaman en fazla i değerine eşittir. Böylece bir değeri okumadan önce üzerine yazmazsın. Tek geçiş O(n) zaman alır ve döndürülen değerler dışında iki tamsayı kullanırsın: O(1) ek alan.

Algoritma

k = 1 olarak ayarla: nums[0] her zaman korunur.
i değerini 1'den son indekse kadar döngüye sok.
nums[i], nums[k-1] değerinden farklıysa nums[k] = nums[i] olarak ayarla ve k değerini 1 artır.
nums dizisinin ilk k değerini döndür.

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]

Tuzaklar ve uç durumlar

Yazma işaretçisi kısadır ve hataları hangi değerle karşılaştırma yaptığınızla ilgilidir.

i son dizine kadar ilerlerken nums[i] ile nums[i+1] değerlerini karşılaştırmak. Son karşılaştırma, dizinin sonunun bir sonrasındaki konumu okur.
k değerini 0'dan başlatmak. Böylece ilk değer nums[-1] ile karşılaştırılır; bu değer aralık dışındadır ya da Python'da son elemandır.
Dizinin tamamını, ilk k değeri yerine döndürmek. Sondaki bölüm eski değerleri hâlâ içerir, bu yüzden [1, 1, 2], [1, 2, 2] olarak döner.
Yanıtı bir hash kümesi üzerinde yineleme yaparak oluşturmak. Çoğu dilde hash kümesi sıralamayı korumaz, bu yüzden değerler karışık sırada gelebilir; bunun yerine, her değerle ilk karşılaştığınızda onu bir listeye ekleyin.
Lua ve R'de diziler 1'den başlar. Korunan bölüm nums[1] ile nums[k] arasındadır ve karşılaştırma nums[k-1] ile değil, nums[k] ile yapılır.

Sıkça sorulan sorular4

Sıralı Diziden Yinelenenleri Kaldırma işleminin zaman karmaşıklığı nedir?

Yazma işaretçisi çözümü her değeri bir kez okur, bu nedenle O(n) zamanda çalışır. Döndürdüğü değerlerin yanı sıra, O(1) ek alan kullanır: iki indeks.

Dizinin neden sıralanması gerekiyor?

Sıralama, bir değerin tüm kopyalarını tek bir grup hâline getirir; bu nedenle bir değer, yalnızca saklanan son değerden farklı olduğunda yenidir. Sıralanmamış bir dizide bir kopya, ilk kopyadan çok uzakta görünebilir ve görülen her değeri hatırlamak için O(n) ek alan kullanan bir karma kümesine ihtiyaç duyarsın.

Ek bellek kullanmadan yinelenenleri yerinde nasıl kaldırırsınız?

Okuma indeksinin yanında bir yazma indeksi k tut. İlk k yuva, şimdiye kadar görülen farklı değerleri tutar. Okuduğun değer nums[k-1] değerinden farklı olduğunda, onu nums[k] konumuna kopyala ve k değerini ilerlet. Yazma indeksi hiçbir zaman okuma indeksini geçmez; böylece hiçbir şey okunmadan önce üzerine yazılmaz.

Her bir değerin en fazla iki kez kullanılmasına nasıl izin verirdiniz?

Bir önceki yerine, tutulan kısımda iki sıra önceki değerle karşılaştırın: k < 2 olduğunda veya nums[i], nums[k-2] değerinden farklı olduğunda nums[i] değerini kopyalayın. Eşitse, tutulan kısım zaten bu değerin iki kopyasıyla bitiyordur. Aynı fikir, nums[k-m] kullanarak en fazla m kopyaya izin verir.

Python

def removeDuplicates(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

[1, 2, 3]