Một câu đố về cấu trúc dữ liệu

Question

Tôi phải đối mặt với câu hỏi puzzle [related to data structure] này trong một cuộc cạnh tranh mã hóa.

Có một hành tinh của cây (cây thực không phải cấu trúc dữ liệu cây !!). Nó có hàng tỉ hay thậm chí hàng tỉ tỷ cây. Nhà vua ra lệnh tìm trung vị của các lứa tuổi (tính theo năm và số nguyên) của tất cả các cây bằng cách sử dụng carbon hẹn hò. (Method does not matter.) Lưu ý: Trung bình là "số giữa" trong danh sách số được sắp xếp.

ràng buộc:
1. Cây lâu đời nhất được biết đến là 2000 năm tuổi.
2. Chúng có một máy duy nhất có thể lưu trữ các số nguyên trong phạm vi từ-vô cực đến + vô cùng.
3. Nhưng số lượng các số nguyên như vậy có thể được lưu trữ trong bộ nhớ tại một thời điểm là 1 triệu.

vì vậy, khi bạn lưu trữ 1 triệu số nguyên để lưu trữ số nguyên tiếp theo, bạn phải xóa một số đã lưu trữ.
Vì vậy, bằng cách nào đó họ phải theo dõi trung bình khi họ tiếp tục đếm tuổi cây.
Làm cách nào để thực hiện việc này?

cách tiếp cận của tôi
Sử dụng một biến thể của loại bên ngoài để sắp xếp các lứa tuổi trong khối & viết chúng trong tập tin.
Áp dụng hợp nhất k-cách [cho các đoạn].
Vấn đề với cách tiếp cận trên là cần quét hai tệp.

tôi có thể nghĩ đến cách tiếp cận khác trong đó sử dụng các thông tin The oldest tree is known to be 2000 years old.
chúng ta không thể mất một count array [as range of ages of tree is fixed]?

Tôi muốn biết có cách tiếp cận nào tốt hơn không?
Liệu có tồn tại bất kỳ phương pháp mà chúng ta không cần để lưu trữ các dữ liệu trong file? [where only main memory is sufficient?]

Answer 1

Bạn có thể làm điều này bằng cách lưu trữ chỉ 2001 số nguyên. Tạo một mảng ở các độ tuổi khác nhau có thể

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

khi bạn đếm một cây

ages[thisAge]++ 

Sau đó tính toán trung bình là tầm thường. Bạn dường như đã nhấn vào giải pháp này trong phương pháp tiếp cận thứ hai mà bạn đề cập đến, nhưng sau đó bạn nói Tôi muốn biết có cách tiếp cận nào tốt hơn không?

Liệu có tồn tại bất kỳ phương pháp mà chúng ta không cần phải lưu trữ dữ liệu trong file? [Nơi chỉ bộ nhớ chính là đủ?]

Tôi không undertstand lý do tại sao bạn hỏi nếu có tồn tại bất kỳ phương pháp nào mà bộ nhớ chính là đủ. Không phải là một mảng của số nguyên 2001 phù hợp trong bộ nhớ chính?

Sử dụng phương pháp trên, bạn có thể điền vào số lượng của mình, sau đó tính trung bình bằng cách lặp lại thông qua số lượng, giữ tổng số tiền khi bạn đi. Khi tổng của bạn đạt đến một nửa tổng số cây, bạn có trung bình. Điều này đòi hỏi phải vượt qua tất cả các cây để đếm, cộng với một phần đi qua một phần của dãy số đếm của một số số < = 2001. Đây là O (n). Bạn có thể, thay vào đó, theo dõi các trung bình với mảng này khi bạn đi, nhưng nó sẽ không thực sự cải thiện về giải pháp.

Answer 2

Cách tiếp cận bạn đề xuất (một mảng năm 2001) là O (n), với một thao tác nhanh trên mỗi cây, do đó tối ưu.

Vâng, gần như tối ưu. Tại một số thời điểm trong khi đếm số cây còn lại sẽ không đủ để thay đổi kết quả. Ví dụ, nếu tôi đếm một nửa + 1 cây, và tất cả đều chính xác 100 tuổi, thì tôi có câu trả lời của tôi: 100 năm.

Nhưng nếu cây được phân tán theo độ tuổi thì số lượng cây được yêu cầu sẽ gần với tổng số.