Başka bir listenin sırasına göre sırala
Görev tanımı
Problem
Bir mağaza stok kodlarını pazarlama ekibinin tercih ettiği bir sıraya göre sıralıyor. values ve birbirinden farklı kodlardan oluşan bir order listesi verildiğinde, values'u order'da görünen kodlar önce, gruplanmış halde ve order'la aynı sırada gelecek, ardından diğer her kod artan sırada gelecek şekilde yeniden diz. İki liste de en fazla 1.000 öğe tutuyor, order'daki her kod values'ta da görünüyor ve her kod 0 ile 1.000 arasında.
Örnekler
Input: values = [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], order = [2, 1, 4, 3, 9, 6]
Output: [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
Neden: 7 ve 19 order'da yok, bu yüzden artan sırada en sona gider
Input: values = [28, 6, 22, 8, 44, 17], order = [22, 28, 8, 6]
Output: [22, 28, 8, 6, 17, 44]
Input: values = [5, 5], order = []
Output: [5, 5]
Neden: edge case: boş bir order ile sonuç düz bir artan sıralamadır
İpuçları
0 / 3
Kodlar küçük tam sayılar; yani onları karşılaştırmak yerine her birinin kaç kez göründüğünü sayabilirsin.
Sayılar elindeyken çıktı yalnız bir dolaşmadır: önce order boyunca, sonra 0'dan yukarı bütün kodlar boyunca.
order'daki her kod için onu sayıldığı kadar çıkar ve sayısını 0'a ayarla. Sonra 0'dan 1.000'e tara ve kalan sayıları çıkar.
- Hedef zaman
- O(n + k)
- Hedef alan
- O(n + k)
Kısıtlar
- values.length ≤ 1,000 and order.length ≤ 1,000
- 0 ≤ code ≤ 1,000
- codes in order are distinct
- every code in order also appears in values
Çözüm
Her kod 0 ile 1.000 arasında olduğu için bir sayma dizisi karşılaştırmaların yerini tamamen alır. values üzerinde bir geçiş her kodun kaç kopyası olduğunu kaydeder. Sonra order'ı dolaşmak her tercih edilen kodu doğru sayıda çıkarır; sayısını sıfırlamak da yeniden çıkarılmamasını sağlar. Bütün olası kodlar üzerinde düşükten yükseğe son tarama artakalanları artan sırada çıkarır; problemin istediği son kısım da tam olarak bu. k = 1.001 olası kodla zaman O(n + k), ek alan O(k).
def relative_sort(values, order, top=1000):
counts = [0] * (top + 1)
for v in values:
counts[v] += 1
out = []
for code in order: # preferred codes first, grouped
out += [code] * counts[code]
counts[code] = 0
for code in range(top + 1): # the rest, ascending
out += [code] * counts[code]
return out
print(relative_sort([2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], [2, 1, 4, 3, 9, 6])) # -> [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
print(relative_sort([28, 6, 22, 8, 44, 17], [22, 28, 8, 6])) # -> [22, 28, 8, 6, 17, 44]
print(relative_sort([5, 5], [])) # -> [5, 5]Kodda değil de fikirde mi takıldın? Counting sort bunu anlatıyor.