Sıralı listede tekrarları at
Görev tanımı
Problem
Bir tam sayı listesi azalmayan sırada sıralı geliyor; yani eşit değerler yan yana, bloklar halinde duruyor. Listeyi in-place (yerinde) sıkıştır: birbirinden farklı her değer orijinal sırasıyla tam bir kez görünsün. Farklı değerlerin sayısı k'yı döndür; ilk k hücre bu değerleri tutmalı, sonrasında kalanlar önemsiz.
Örnekler
Input: nums = [1, 1, 2, 3, 3, 3]
Output: 3, and nums begins with [1, 2, 3]
Input: nums = [4, 4, 4]
Output: 1, and nums begins with [4]
Neden: tek bir uzun blok tek bir değere iner
Input: nums = []
Output: 0
Neden: edge case: boş liste hiçbir şey tutmaz
İpuçları
0 / 3
Zor kısmı sıralama zaten yaptı: bir tekrar ancak ikizinin hemen yanında durabilir, yani hiçbir zaman bütün listeyi aramak zorunda değilsin.
Aynı liste üzerinde farklı hızlarda ilerleyen iki konum tut: biri her elemana bakar, diğeri bir sonraki tutulacak değerin nereye yazılacağını gösterir.
Okuma konumunu liste boyunca ilerlet. Oradaki değer en son tuttuğun değerden farklıysa onu yazma konumuna kopyala ve yazma konumunu bir ilerlet. Sonunda yazma konumu, farklı değerlerin sayısına eşit olur.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- nums is sorted in non-decreasing order
- compact the list in place
Çözüm
Aynı listeyi iki indeks dolaşır: okuyucu her elemanı ziyaret eder, yazıcı bir sonraki farklı değerin hücresini gösterir. Sıralı girdide eşit değerler yan yana olduğu için okuyucunun yeni bir bloğu fark etmesi için yalnız en son tutulan değerle karşılaştırması yeter. Kopyalama yalnız blok sınırlarında olur, ek liste ayrılmaz. Zaman O(n), alan O(1).
def compact_sorted(nums):
if not nums: # nothing to keep in an empty list
return 0
write = 1 # slot for the next distinct value
for read in range(1, len(nums)):
# sorted input means a new value shows up only at a run boundary
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
a = [1, 1, 2, 3, 3, 3]
print(compact_sorted(a), a[:3]) # -> 3 [1, 2, 3]
b = [4, 4, 4]
print(compact_sorted(b), b[:1]) # -> 1 [4]
print(compact_sorted([])) # -> 0Kodda değil de fikirde mi takıldın? İki pointer bunu anlatıyor.