Geçenlerde "programı, 1 milyar sayı dizisi 100 büyük numaraları öğrenmek için yazıyorum." istemiştim mülakata katıldı

(Nlogn) O zaman karmaşıklığı diziyi sıralamak ve son 100 sayı alacak olan kaba kuvveti bir çözüm vermek için sadece mümkün oldu.

Arrays.sort(array);

Görüşmeci daha iyi bir zaman karmaşıklığı arıyordu, diğer birkaç çözüm yolu denedim ama cevap veremedi. Zaman karmaşıklığı daha iyi bir çözüm var mı?

Sen-ebilmek tutmak bir öncelik sırası 100 büyük sayılar, yineleme yoluyla milyar numaraları, her karşılaşma bir numara daha büyük olan en küçük sayı sıra (baş ve kuyruk), Kaldır başını sıraya Ekle yeni sayısı için sıraya.

DÜZENLEME: Dev belirtildiği gibi, bir öncelik sırası bir yığın ile uyguladığı sıraya ekleme karmaşıklığı O(logN)

En kötü durumda billion*log2(billion) iyidir billion*log2(100) olsun

Genel olarak, eğer ihtiyacınız olan en büyük K sayıları kümesi N numaraları, karmaşıklığı O(NlogK) yerine O(NlogN), Bu çok önemli zaman K çok küçük karşılaştırarak N

EDİT2:

Bu algoritmanın beklenen süresi her tekrarında bir ekleme olabilir ya da oluşabilir beri oldukça ilginç. Olasılık ben'inci sayısı eklenecek için kuyruk olasılık rasgele bir değişken olmak daha büyük en az i-K rasgele değişkenlerin aynı dağılımı (ilk k numaraları otomatik olarak eklenen sıra). Sıra istatistikleri (link) bu olasılık hesaplamak için kullanabiliriz. Örneğin, hadi varsayalım numaraları vardı rasgele seçilen düzgün {0, 1} beklenen değeri (ı-K)th numara (ı numara) (i-k)/i ve şans bir rasgele değişken olmak daha büyük bu değer 1-[(i-k)/i] = k/i.

Böylece, eklemeler sayısıdır

Ve beklenen çalışma süresi olarak ifade edilebilir:

(k zaman oluşturmak için sıra ile ilk k elemanları, n-k karşılaştırmalar, ve beklenen sayıda eklemeler yukarıda açıklandığı gibi, her alır ortalama log(k)/2 zaman)

N çok büyük K Bu ifade için karşılaştırma yaparken çok NlogK yerine n daha yakın olduğunu unutmayın. Bu biraz sezgisel olarak dava konusu bile sonra 10000 yineleme (ki çok küçük karşılaştırmak için bir milyar), şans sayısı eklenecek sıraya çok küçük.