Move Zeroes

Q: Sıfırları, diğer öğelerin sırasını değiştirmeden sona nasıl taşırsınız?

Öndeki bir sonraki boş konum için bir write dizini tut ve ikinci bir dizinle tara. Bulduğun sıfır olmayan her değer write konumundaki değerle yer değiştirir ve write bir adım sağa ilerler. Değerler bulduğun sırayla yerleştirilir, bu yüzden göreli sıraları asla değişmez.

Q: Sıfırları Taşıma işlemi daha az yazma işlemiyle yapılabilir mi?

Evet. Yer değiştirmek yerine, sıfır olmayan her değeri nums[write] konumuna kopyala ve tarama bittikten sonra write konumundan sona kadar olan her yeri 0 ile doldur. Böylece her konuma en fazla bir kez yazılır. read , write değerine eşitse yer değiştirmeyi de atlayabilirsin; çünkü bu işlem bir değeri zaten bulunduğu yere geri koyar.

Kolayİki işaretçi

+10

Bir tamsayı dizisi olan nums veriliyor. Her 0'ı dizinin sonuna taşı ve diğer değerleri mevcut sıralarını koruyacak şekilde bırak. nums ile aynı uzunluğa sahip, yeniden düzenlenmiş diziyi döndür.

Fonksiyon

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

numsinteger-array: yeniden düzenlenecek tamsayı dizisi
Döndürürinteger-array: sıfır olmayan değerler önce, özgün sıraları korunarak ve tüm 0’lar sonda olacak şekilde nums

Kısıtlar

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Örnekler

Girdi: nums = [0, 4, 0, 7, 2]
Çıktı: [4, 7, 2, 0, 0]
Açıklama: 0 olmayan değerler 4, 7 ve 2'dir ve başta bu sırayı korurlar. İki 0 son iki yeri doldurur.

Gönderirken +14 gizli test

Ek soru

Diğer değerleri sıralarını koruyarak tek geçişte ve O(1) ek bellek kullanarak her 0 değerini başa taşıyabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Sıfırları sona taşımak zor kısım değildir. Zor olan, diğer değerleri özgün sıralarında tutmaktır; bu nedenle her 0'ı son öğeyle değiştirmek işe yaramaz. Diziyi, şimdiye kadar bulunan sıfır olmayan değerleri tutan bir ön bölgeye ve geri kalan bölgeye ayırın. Bir dizin her öğeyi okur, ikinci bir dizin bir sonraki sıfır olmayan değerin nereye ait olduğunu işaretler ve tek bir geçişte işlem yerinde tamamlanır.

Sıfır olmayan değerleri kopyalayın

Sezgi

Yeni bir dizi oluştur. nums üzerinde ilerle ve 0 olmayan her değeri, karşılaştığın sırayla kopyala. Ardından yeni dizi nums kadar uzun olana dek sıfırlar ekle. Eklediğin sıfırların sayısı, atladığın sayı kadardır.

[0, 4, 0, 7, 2] için kopyalama adımı [4, 7, 2] sonucunu verir ve iki sıfır eklenince [4, 7, 2, 0, 0] olur. Değerleri okuduğun sırayla kopyaladığın için sıralama doğrudur.

Her eleman bir kez okunup bir kez yazılır, bu nedenle zaman karmaşıklığı O(n)'dir. İkinci dizi O(n) bellek kullanır; sonraki yaklaşım bunu önler.

Algoritma

Boş bir sonuç dizisi oluştur.
nums içindeki her değer için, 0 değilse onu sonuca ekle.
Sonuçta nums ile aynı sayıda öğe olana kadar sıfır ekle.
Sonucu döndür.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

İki işaretçi, yerinde takas

Sezgi

İki indeks kullanın. read, her öğeyi soldan sağa ziyaret eder. write, sıradaki sıfır olmayan değerin yerleşeceği yeri işaretler. Her adımdan sonra iki koşul sağlanır: write öncesindeki her şey, şimdiye kadar görülen sıfır olmayan değerlerden oluşur ve özgün sıraları korunur; write ile read arasındaki her şey 0'dır.

nums[read] 0 değilse onu nums[write] ile takas edin ve write değerini bir adım sağa ilerletin. read konumuna gelen değer, sıfır bölgesinden gelen bir 0'dır ya da iki indeks eşitse aynı değerdir. Sıfır olmayan değerler yalnızca sıfırların üzerinden atlar, birbirlerinin üzerinden asla atlamaz; bu yüzden sıraları korunur.

[0, 4, 0, 7, 2] dizisinde: 1. indeksteki 4, 0. indeksteki değerle takas edilir ve sonuç [4, 0, 0, 7, 2] olur. 3. indeksteki 7, 1. indeksteki değerle takas edilir ve sonuç [4, 7, 0, 0, 2] olur. 4. indeksteki 2, 2. indeksteki değerle takas edilir ve sonuç [4, 7, 2, 0, 0] olur. Tek geçiş ve ikinci bir dizi kullanmadan: O(n) zaman ve O(1) bellek.

Algoritma

write değerini 0 olarak ayarla.
read değerini ilk indexten son indexe taşı.
nums[read] 0 değilse, nums[read] ile nums[write] değerlerini yer değiştir, ardından write değerini 1 artır.
nums değerini döndür.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Tuzaklar ve uç durumlar

Olağan hatalar ya diğer değerlerin sırasını bozar ya da öğeleri atlar.

Her 0 değerini son öğeyle değiştirmek sıfırları taşır ama geri kalanını karıştırır: [0, 4, 7], [7, 4, 0] olur.
Bir indeks dizide ilerlerken sıfırları diziden silmek öğelerin atlanmasına yol açar. [0, 0, 5] dizisinde, 0 indeksini silmek ikinci 0 değerini 0 indeksine kaydırırken döngü 1 indeksine ilerler. Her silme işlemi dizinin geri kalanını da kaydırır ve bu da döngüyü O(n²) yapar.
x > 0 yerine x != 0 koşulunu test edin. Negatif değerler sıfır değildir: [-1, 0, -2] dizisi [-1, -2, 0] olmalıdır; ancak x > 0 kullanıldığında kopya sürümü [0, 0, 0] sonucunu döndürür.
Sıfır içermeyen veya yalnızca sıfırlardan oluşan bir dizi değişmeden geri dönmelidir. Takas sürümünde, ilk 0 değerine kadar read ve write eşit kalır; bu nedenle bu takaslar hiçbir şeyi değiştirmez.
Lua ve R'de diziler 1'den başladığı için write da 1'den başlar.

Sıkça sorulan sorular4

Sıfırları Taşıma işleminin zaman karmaşıklığı nedir?

O(n). Her iki yaklaşım da her öğeyi bir kez okur. Sıfır olmayan değerleri yeni bir diziye kopyalamak O(n) ek bellek gerektirirken, iki işaretçili takas işlemi dizi içinde O(1) ek bellekle çalışır.

Sıfırları, diğer öğelerin sırasını değiştirmeden sona nasıl taşırsınız?

Öndeki bir sonraki boş konum için bir write dizini tut ve ikinci bir dizinle tara. Bulduğun sıfır olmayan her değer write konumundaki değerle yer değiştirir ve write bir adım sağa ilerler. Değerler bulduğun sırayla yerleştirilir, bu yüzden göreli sıraları asla değişmez.

Sıfırları Taşıma işlemi daha az yazma işlemiyle yapılabilir mi?

Evet. Yer değiştirmek yerine, sıfır olmayan her değeri nums[write] konumuna kopyala ve tarama bittikten sonra write konumundan sona kadar olan her yeri 0 ile doldur. Böylece her konuma en fazla bir kez yazılır. read, write değerine eşitse yer değiştirmeyi de atlayabilirsin; çünkü bu işlem bir değeri zaten bulunduğu yere geri koyar.

Sıfırları Taşı neden iki işaretçili bir problemdir?

Bir işaretçi her öğeyi okur, diğeri ise tamamlanmış ön bölümün sonunu işaretler. İkisi de yalnızca ileri doğru hareket eder, bu yüzden birlikte tek bir geçiş yaparlar. Aynı okuma ve yazma düzeni, sıralanmış bir dizideki yinelenen öğeleri kaldırır veya bir dizideki herhangi bir değeri yerinde filtreler.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [0, 4, 0, 7, 2]

Beklenen

[4, 7, 2, 0, 0]