Microsoft ile bir röportaj da bu sorun var.

Rasgele sayı dizisi verildiğinde, kaldırır C bir algoritma yazmak sayı yinelenen ve özgün benzersiz numaralar dönüş dizi.

E. g Giriş: {4, 8, 4, 1, 1, 2, 9} Çıkış: {4, 8, 1, 2, 9, ?, ?}

Bir uyarı beklenen algoritma ilk sıralanacak dizi değil gerekli olmasıdır. Ve bir unsur çıkarıldığı zaman, aşağıdaki unsurlar öne de değiştirdi olmalıdır. Neyse, unsurlar öne kaydırıldı nerede dizisi kuyruk elemanlarının değeri yok denecek kadar azdır.

Güncelleme:Sonuç orijinal dizi içinde iade edilmelidir ve yardımcı veri yapısı (örneğin, karma tablo) kullanılmamalıdır. Ancak, düzenin korunması gerekli değil sanırım.

Update2:Neden bu pratik kısıtlamaları merak edenler için, bu röportaj bir soru oldu ve tüm bu kısıtlamaları düşünme sürecinde farklı fikirler nasıl uyar tartışılır.

Bir çözüm kız arkadaşım tarafından önerilen sıralama birleştirme çeşididir. Tek değişiklik sırasında adım birleştirme, sadece yinelenen değerleri göz ardı edilir. Bu çözüm de O(n log n) olur. Bu yaklaşım, sıralama/çoğaltma kaldırılması için bir araya birleştirilir. Ancak, eğer herhangi bir fark yapar emin değilim.