Sort List
Aynı uzunluktaki iki dizide saklanan tek yönlü bağlı bir liste veriliyor. i düğümü values[i] değerini tutar ve next[i] düğümüne bağlanır, -1 listenin sonunu belirtir ve baş düğüm 0'dır. Düğümler liste sırasına göre saklanmaz ve dizilerde, 0 düğümünden başlayarak ilerlerken hiç ulaşılamayan artık düğümler de bulunabilir. Bağlantıları listeye işaret etse bile bunlar listenin parçası değildir.
Listeyi değerlerine göre azalmayan sırada sıralayın ve düğümlerinin değerlerini bu sırayla döndürün.
Fonksiyon
- nextinteger-array
- her düğümün bağlantı verdiği düğümün dizini veya son düğüm için -1
- valuesinteger-array
- her bir düğümün tuttuğu değer
- Döndürürinteger-array
- listenin düğümlerinin değerleri, en küçükten başlayarak
Kısıtlar
1 ≤ n ≤ 4000; buradan,nextvevaluesuzunluğudur.-1000 ≤ values[i] ≤ 1000- Her
next[i],-1veya0ilen-1arasında bir düğüm indeksidir. - Başlangıç düğümü
0olan liste, hiçbir düğümü iki kez ziyaret etmeden-1değerine ulaşır. - Düğüm
0'dan başlayan yürüyüşün ulaşmadığı düğümler listenin parçası değildir. Bunlarınnextgirdileri herhangi bir yeri gösterebilir.
Örnekler
- Girdi
- next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
- Çıktı
- [1, 2, 3, 4, 5]
- Açıklama
0düğümünden başlayan yürüyüş0, 3, 2, 4, 1düğümlerini ziyaret eder; dolayısıyla liste4, 2, 3, 5, 1şeklindedir. Sıralandığında1, 2, 3, 4, 5olur.
- Girdi
- next = [2, 0, -1, -1]values = [6, 9, -2, 5]
- Çıktı
- [-2, 6]
- Açıklama
- Liste
0 → 2şeklindedir; bu da6, -2olarak okunur.1ve3düğümlerine baştan hiçbir zaman ulaşılmaz; bu nedenle1düğümü0düğümüne bağlı olsa bile9ve5değerleri dışarıda kalır.
- Girdi
- next = [1, 2, 3, -1]values = [3, -1, 3, -1]
- Çıktı
- [-1, -1, 3, 3]
- Açıklama
- Liste
3, -1, 3, -1şeklindedir. Eşit değerler, göründükleri sayıda yanıtta kalır:-1, -1, 3, 3.
Ek soru
Sıralı değerleri kopyalamadan, O(n log n) sürede düğümleri yeniden bağlayarak sıralama yapabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Hangi sıralama algoritmalarının rastgele bir konuma atlaması gerekir, hangileri ise girdileri boyunca yalnızca ileri doğru ilerler? Bağlı liste ikinci türde iyidir.
Sıralı iki listeyi tek bir listede birleştirmek için ek belleğe gerek yoktur: Düğümleri yeniden bağlar ve her zaman iki baştaki değerden küçük olanı alırsın. Listeyi sıralı iki yarıya bölebilseydin, tek bir birleştirme işi bitirirdi.
Yavaş ve hızlı birer işaretçi kullanarak ortayı bulun ve listeyi oradan kesin. Tek bir düğüme ulaşana kadar her yarıyı aynı şekilde sıralayın; tek düğüm zaten sıralıdır. Ardından sıralanmış iki yarıyı birleştirin ve yeni başı döndürün.
Çözüm
Quicksort ve heapsort rastgele erişime dayanır, tek yönlü bağlı bir liste ise yalnızca ileri doğru ilerler. Merge sort uygundur: bir listeyi ortasından bölmek ve sıralanmış iki listeyi birleştirmek için ileri doğru ilerlenir; böylece bağlantıların kendisi O(n log n) sürede sıralanır. Burada n, dizilerin uzunluğudur.
Değerleri bir diziye kopyalayın ve sıralayın
Sezgi
Liste, node = next[node] adımının 0 düğümünden başlayıp -1 değerine ulaşana kadar ziyaret ettiği değerlerden oluşur. Bu değerleri yeni bir diziye topla, yerleşik sıralama işleviyle sırala ve diziyi döndür. values değerini doğrudan sıralayamazsın: ikinci örnekte bu değişken, listede bulunmayan 9 ve 5 değerlerini içerir.
Adım O(n), sıralama ise O(n log n) zaman alır ve O(n) ek bellek kullanır. Listenin kendisine hiç dokunulmaz; görüşmecilerin bir sonraki yaklaşımı sormasının nedeni budur.
Algoritma
- Boş bir dizi ve
node = 0ile başla. node,-1olmadığı sürecevalues[node]değerini ekle venext[node]konumuna ilerle.- Diziyi artan sırada sırala ve döndür.
def sortList(next, values):
# Collect the values of the nodes on the list, then sort them.
on_list = []
node = 0
while node != -1:
on_list.append(values[node])
node = next[node]
on_list.sort()
return on_listBağlantılarda birleştirme sıralaması
Sezgi
Bir bağlantı ilerleyen yavaş işaretçi ile iki bağlantı ilerleyen hızlı işaretçi, tek geçişte ortayı bulur. Sıralı iki listeyi birleştirmek için yalnızca baş düğümleri gerekir: küçük olanı alıp ilerle. Bu adımların hiçbiri ikinci bir dizi gerektirmez.
İlk örnekte slow, 3 üzerinde durur ve bağlantısını kesmek 4, 2, 3, 5, 1 listesini 4, 2, 3 ve 5, 1 olarak böler. Bunlar sırasıyla 2, 3, 4 ve 1, 5 olarak sıralanır; birleştirme 1, 2, 3, 4 değerlerini alır, ardından kalan 5 değerini bağlar.
Bölmenin her düzeyinde her düğüme sabit sayıda dokunulur ve yaklaşık log n düzey vardır; dolayısıyla süre O(n log n) olur. Tek ek bellek, özyineleme yığınıdır; 4000 düğüm için yaklaşık 12 çağrı derinliğindedir.
Algoritma
- Listede tek bir düğüm varsa (
next[head] == -1),headdeğerini döndür. slow = headvefast = next[head]olarak başlat;fastvenext[fast],-1olmadığı süreceslow'u bir bağlantı,fast'i iki bağlantı ilerlet.second = next[slow]olarak belirle venext[slow] = -1ile kes.- Her iki yarıyı da özyinelemeli olarak sırala. Bunları birleştir: yarılardan biri boşalana kadar daha küçük olan öndeki düğümü
tail'in arkasına bağla, ardından diğer yarının kalanını bağla. - Döndürülen baştan başlayarak ilerle ve değerleri topla.
def sortList(next, values):
def merge(a, b):
# Splice two sorted lists into one; on a tie the node from a goes first.
head = tail = -1
while a != -1 and b != -1:
if values[b] < values[a]:
node, b = b, next[b]
else:
node, a = a, next[a]
if tail == -1:
head = node
else:
next[tail] = node
tail = node
next[tail] = a if a != -1 else b # attach whatever is left
return head
def sort(head):
if next[head] == -1: # one node is already sorted
return head
# slow stops on the last node of the first half
slow, fast = head, next[head]
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
return merge(sort(head), sort(second))
result = []
node = sort(0)
while node != -1:
result.append(values[node])
node = next[node]
return result
Tuzaklar ve uç durumlar
valuesdizisinin tamamını sıralamak. İkinci örnekte, listede bulunmayan9ve5değerleri de eklenir.fastişaretçisini baş düğümden başlatmak. İki düğüm olduğundaslowikinci düğüme ulaşır, kesme işlemi ikinci yarıyı boş bırakır ve özyineleme hiç küçülmez.next[slow] = -1kesmesini unutmak. Böylece ilk yarı ikinci yarıya kadar uzanır ve her iki çağrı da örtüşen listeleri sıralar.- Diğer yarı tükendiğinde bir yarının geri kalanını atmak. Bu düğümler sonuçta kaybolur.
- Lua ve R'de diziler 1'den başlar: düğüm indekslerini 0 tabanlı tutun ve
next[node + 1]üzerinden okuyun. R sürümü bağlantı dizisini bir kez kopyalar; bu nedenle O(n) ek bellek kullanır.
Sıkça sorulan sorular3
Bağlı bir listeyi sıralamanın en iyi yolu nedir?
Birleştirmeli sıralama. Ortadan bölmek, her iki yarıyı sıralamak ve bunları birleştirmek, listenin başından sonuna doğru ilerler; tek yönlü bağlı bir listenin desteklediği tek yön budur. O(n log n) zamanda çalışır ve mevcut düğümleri yeniden bağlar.
Bağlı listeler için neden birleştirme sıralaması hızlı sıralamaya tercih edilir?
Quicksort, bağlantıları yeniden kurarak bir listeyi bölümlere ayırabilir; ancak iyi bir pivot rastgele erişim gerektirir ve başı pivot olarak seçmek, sıralı bir listenin maliyetini O(n²) yapar. Merge sort listeyi her zaman ikiye böler, bu nedenle her türlü girdide O(n log n) karmaşıklığında kalır.
Bağlı bir listeyi O(n log n) zamanda ve O(1) bellek kullanarak sıralayabilir misin?
Evet, aşağıdan yukarıya birleştirmeli sıralama ile. Uzunluğu 1 olan komşu dizileri, sonra 2, ardından 4 uzunluğunda olanları birleştirir; bu işlem tek bir dizi listeyi kaplayana kadar sürer. log n doğrusal geçiş vardır ve kullanılan tek bellek birkaç düğüm indeksidir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def sortList(next, values):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
next = [3, -1, 4, 2, 1] values = [4, 1, 3, 2, 5]
Beklenen Çıktı
[1, 2, 3, 4, 5]