Hedef değerleri sona it
Görev tanımı
Problem
Bir çalma listesi editörü, bir şarkı id'sinin bütün kopyalarını başka hiçbir şeyi karıştırmadan kuyruğun sonuna taşımak istiyor. Bir nums listesi ve bir v değeri verildiğinde listeyi in-place (yerinde) yeniden düzenle: v'den farklı elemanlar önde, orijinal göreli sıralarını koruyarak dursun, v'nin her kopyası da arkada. Aynı liste nesnesini döndür ve yalnız sabit miktarda ek bellek kullan.
Örnekler
Input: nums = [4, 0, 7, 0, 2], v = 0
Output: [4, 7, 2, 0, 0]
Neden: 4, 7 ve 2 geldikleri sırada kalır
Input: nums = [3, 1, 3, 3, 5], v = 3
Output: [1, 5, 3, 3, 3]
Neden: 3'ün üç kopyası arkada toplanır
Input: nums = [], v = 9
Output: []
Neden: edge case: taşınacak bir şey yok
İpuçları
0 / 3
Tutulacaklar için ikinci bir liste, kopyalar için bir başkasını kurmak işe yarar, ama görev sabit ek bellek istiyor. Bir sonraki tutulacak değerin nereye yazılması gerektiğini düşün.
Aynı listede iki indeks kullan: biri her elemanı okur, diğeri bir sonraki tutulacak değerin yazılacağı hücreyi gösterir.
Soldan sağa oku ve v'den farklı her elemanı yazma hücresine kopyala, her seferinde yazma indeksini ilerlet. Okuyucu bitince yazma indeksinden sona kadar her hücreyi v ile doldur.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- rearrange in place with O(1) extra memory
- other values keep their relative order
Çözüm
Yazma indeksi yalnız bir değer tutulduğunda ilerler; bu yüzden okuyucuyu hiçbir zaman geçmez ve hiçbir değer okunmadan üzerine yazılmaz. Okuma sırasıyla kopyalamak, tutulan değerlerin göreli sırasını bedavaya korur. Son tutulan değerden sonraki her hücre v'nin bir kopyasını tutmalıdır, çünkü kopya sayısı geriye kalan hücre sayısına eşittir. Tek geçiş artı doldurmayla zaman O(n), alan O(1).
def push_back(nums, v):
write = 0 # slot for the next value we keep in front
for x in nums:
if x != v:
nums[write] = x # copy forward, order is preserved
write += 1
for i in range(write, len(nums)):
nums[i] = v # the leftover slots belong to v
return nums
print(push_back([4, 0, 7, 0, 2], 0)) # -> [4, 7, 2, 0, 0]
print(push_back([3, 1, 3, 3, 5], 3)) # -> [1, 5, 3, 3, 3]
print(push_back([], 9)) # -> []Kodda değil de fikirde mi takıldın? Sıfırları sona taşıma bunu anlatıyor.