O (n) saatinde sıralamak için dizide veri nasıl kaydedilir?

Question

Bir oyunda, bir kullanıcı her turda numaralarını n sayaçlarından (1,2,...,n numaralı numara) bir sayaca ekleyebilir. Bu oyun için o vardır:

• sayacın i içeriğini döndüren bir fonksiyon counter(i). O(1) zamanında.

• add(i) işlevini, i sayacını arttıran bir işlev. O(1) zamanında.

• Kimliklerin sayaç içeriği tarafından azalan sırada sıralanmasını sağlayan bir işlev print(). O(n) zamanında.

Bu oyun O(n) yerine nasıl uygulanır?

Sayaçları dizide tutmam gerektiğini biliyorum, ancak bunları O(n) zamanında nasıl sıralayabilirim?

Answer 1

Bunu bir dizi ve bağlantılı listelerin bağlantılı listesiyle çözebilirsiniz.

Dizi, daha sonra tanımlayacağım sayaç kimliğinden karşı nesneye eşleştiriliyor. Ana liste, her düğümün sayaç miktarını temsil ettiği bir listedir. Her bir düğümün, bu miktarın sahip olduğu tüm karşı-nesnelerin bir listesi vardır, bunların her biri ana listenin düğümüne (miktarını temsil eden düğüm) geri bir göstericiye sahiptir.

Bunu nesne içinde bulunduğu düğümü ulaşmak için sahip olduğunuz işaretçi kullanabilir ve temsil ettiği miktar ne olduğunu görmek için daha sayacı i, sen O(1) zamanlı olarak diziye ile nesneyi alabilirsiniz artmaktadır zaman . Artık sayaç nesnesini ayırabilir ve O(1) zamanında bir sonraki listeye ekleyebilirsiniz (mevcut değilse, böyle bir liste oluşturun).

Baskı basittir ve ana listeyi geçerek O(n) alır.