Veri yapısı üzerinde bir bulmaca

Question

Bir kodlama yarışmasında bu puzzle sorusuna [related to data structure] karşı karşıya kaldım.

Ağaçlar bir gezegen var (gerçek ağaç ağacı yapısı değil!). Milyar hatta trilyonlarca ağaç var. Kral, tüm ağaçların yaşlarını (yılların ve tam sayılarının) ortanca kalma yöntemini kullanarak bulmalarını emreder. (Method does not matter.) Not: Median, sıralı bir sayı listesinde "orta sayıdır".

Kısıtlamalar:
1. en eski ağaç 2000 yaşında olduğu bilinmektedir.
2. Tam sayıları -infinity ile + sonsuz arasında tutabilen tek bir makineye sahipler.
3. Ancak, bellekte depolanabilecek tam sayıların sayısı 1 milyondur.

, bir sonraki depolamak için 1 milyon tamsayı depoladığınızda, önceden depolanmış olanı silmeniz gerekir.
Her nasılsa ağaçların yaşlarını saymaya devam ederken medyanı takip etmek zorundalar.
Bunu nasıl yapabilirler?

Benim yaklaşımım
Kullanım harici tür bir varyant dosyasında yazma & parçalar halinde yaş sıralamak.
[Parçalar için] k yolu birleştirmeyi uygulayın.
Yukarıdaki yaklaşımın problemi, dosyanın iki taramasına ihtiyaç duymasıdır. Ben The oldest tree is known to be 2000 years old.
biz count array [as range of ages of tree is fixed] alamaz bilgileri kullanır başka yaklaşım ait

düşünebilir?

Ben daha iyi bir yaklaşım olduğunu bilmek istiyorum?
Dosyadaki veri depolamak gerekmez herhangi bir yöntem var var mı? [where only main memory is sufficient?]

Answer 1

sadece 2001 tamsayılar depolayarak yapabilirsiniz. Eğer Sonra ortanca önemsiz bilgi işlem bir tree

ages[thisAge]++ 

sayması farklı olası yaşlar

ages[2001] // [0..2000] 

bir dizi oluşturun. Bahsettiğiniz ikinci yaklaşımda bu çözüm üzerinde isabetli görünüyorsunuz, ama daha sonra olduğunu bilmek istiyorum Daha iyi bir yaklaşım var mı? Biz dosyayı veri depolamak gerekmez nerede

herhangi bir yöntem var var mı? [sadece ana bellek yeterli olduğu?]

sen sormak neden undertstand yok orada Ana belleğin yeterli olduğu herhangi bir yöntem vardır. 2001 tamsayı dizisi ana belleğe uymuyor mu?Yukarıdaki yaklaşımı kullanarak

, sayımlar arasında dizinizi doldurmak ve ardından gitmek gibi toplamını tutarak sayıları yineleme ile medyan hesaplayabilirsiniz. Toplamınız toplam ağaç sayısına ulaştığında, medyanız var. Bu, bir saymak tüm ağaçlar girintinin, bir kaç dizi 2001 = < sayma dizisinin bir parçası üzerinden bir geçiş gerektirmektedir. Yani bu O (n). Bunun yerine, bu diziyle medyanı takip edebilirdiniz, ancak çözüm üzerinde gerçekten gelişmez. o en uygunudur böylece

Answer 2

önerilen yaklaşım (2001 yıllık bir dizi), ağacın başına bir hızlı operasyonla O (n) 'dir.

Yani, neredeyse optimum. Sayım sırasında bir noktada, kalan ağaçların sayısı sonucu değiştirmek için yeterli olmayacaktır. Örneğin, ağaçların yarısını + 1 sayıyorsam ve hepsi 100 yaşındaysa, cevabım 100 yıl sonra.

Ama ağaçlar çağında iyi dağılmış, o zaman gerekli ağaç sayısı toplam sayısına yakın olacaktır

.