SORU
26 Ocak 2011, ÇARŞAMBA


Hangi push_rear bir sıra uygulamak () ve pop_front() ve get_min() sabit zaman operasyonlar tüm

Bu soru ile karşılaştım: Hangi push_rear bir sıra uygulamak () ve pop_front() ve get_min() sabit zaman operasyonlardır.

Ben başlangıçta(1) Bir get_min için karmaşıklık O olan min-heap veri yapısı kullanarak düşündüm(). Ama push_rear() ve pop_front() O(log(n)) olur.

Herkes O(1) bas olan böyle bir sıra uygulamak için en iyi yolu ne olacağını(), pop() ve mın()?

Bu konuyu araştırdım ve Algorithm Geeks thread bu işaret etmek istedim. Ama bu çözümlerin hiçbiri 3 yöntemleri için sürekli zaman kural gibi görünüyor: () push, pop() ve mın().

Tüm önerileriniz için teşekkürler.

CEVAP
26 Ocak 2011, ÇARŞAMBA


Stack O(1) pop uygulayabilirsiniz(), push() ve get_min(): sadece mağaza her öğe ile mevcut asgari beraber. Bu yüzden, örneğin, [4,2,5,1] (üst 1) [(4,4), (2,2), (5,2), (1,1)] yığın haline gelir.

O zaman 9**. Bir tane, bir tane daha yığından pop itin; eğer ikinci yığın pop sırasında boş ise, ikinci bir ilk yığından tüm öğeleri taşıyın.

pop bir istek için E. g, ilk [(4,4), (2,2), (5,2), (1,1)], ikinci yığın yığın gelen tüm öğeleri hareketli [(1,1), (5,1), (2,1), (4,1)] olurdu. ve şimdi bir yığın ikinci üst elemanı döndürür.

Sıranın asgari elemanı bulmak için, bireyin en küçük iki element de min-yığınları bak, sonra bu iki değerden en az. (Tabii, burada yığınlarının biri boş ama bu geçici bir çözüm bulmak) çok zor değil bu durumda fazladan bir mantık var.

(1) 7** get_min() push() amortisman Ç(1) O olacak.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • 8lacKy

    8lacKy

    30 Mart 2009
  • Ash100HD

    Ash100HD

    29 EKİM 2011
  • Booredatwork.com

    Booredatwork

    5 Ocak 2009