15 NİSAN 2011, Cuma
Veri yapısı: Ekle, Kaldır, rastgele bir eleman, O hiç(1)içerir
Bir röportajda bu sorunun verildi. Nasıl cevap verir miydin?
O(1) süre: aşağıdaki işlemleri sunan bir veri yapısı tasarımı
- Ekle
- Kaldır
- içerir
- rastgele bir eleman olsun
CEVAP
16 NİSAN 2011, CUMARTESİ
Veri yapısı karma tablo bir H oluşan ve karma tablo anahtarları veri yapısındaki elemanları bir dizi A. düşünün, ve değerleri dizideki konumları.
- Ekle(değer): diziye değer eklemek ve ben A. Set H[değer]=ı. endeks olalım
- Kaldır(Değer): Değer endeksi de A. d son elemanı dizinin son elemanı olarak ile Bir m. içeren hücreyi değiştirmek için gidiyoruz H[değer], kaldırılacak değeri dizideki endeksi de buna izin verdim. Bir dizi[i]=d, H[d]=ben, bir dizinin boyutunu azaltmak ve H. değer çıkarın
- (değer) içerir: iade H. içerir(değer)
- () getRandomElement: r=random(mevcut boyut). [r] dönüş.
dizi otomatik artış boyutu gerekir, çünkü, O(1) bir öğe eklemek için amorti olacak, ama bu sorun değil sanırım.
Bunu Paylaş:
Tamamen işlevsel bir veri yapısı fayda...
dinamik ve viewpager Ekle Kaldır görün...
Birim Testleri rastgele veri?...
Ekle&; style= " display:"blok&quo...
Toplama kümesinden rastgele bir eleman...