Cho N số nguyên bất kỳ, làm cách nào để tìm trung bình nửa trên của các số này? Có một giải pháp O (n)? Nếu không phải là nó có thể chứng minh rằng nó không phải là có thể?Làm cách nào để tìm trung bình một nửa số N trên cùng?
Trước tiên, hãy tìm một median của mảng đã cho (nó takes linear time).
Sau đó, chỉ cần đi qua mảng và tổng hợp tất cả các phần tử lớn hơn trung vị.
Đếm số lượng phần tử bạn đã tổng hợp (M). Nếu M < N/2, thì điều đó có nghĩa là một số phần tử bằng với giá trị trung bình (cụ thể là, N/2 - M) thuộc về nửa trên. Thêm vào tổng của bạn có nhiều giá trị trung bình. Chúng ta cần sự phức tạp này bởi vì chúng ta không biết có bao nhiêu phần tử trung bình (có thể có một vài) thuộc về nửa trên: nếu chúng ta lấy tất cả, chúng ta có thể kết thúc hơn N/2 yếu tố.
Bây giờ bạn có tổng của nửa trên cùng của mảng. Chia cho N/2 và bạn đã hoàn tất.
Hoặc mã có thể đơn giản hơn nếu bạn thực hiện thêm mật mã O (n) và chỉ đếm số phần tử bằng với số trung vị. Điều đó cho bạn biết có bao nhiêu phần tử trung bình bằng nhau để bao gồm ở mức trung bình. –
Thậm chí đơn giản hơn sẽ là sử dụng hầu như bất kỳ thuật toán nào để tìm một trung vị cũng tìm thấy một phân vùng của danh sách đầu vào vào nửa trên. Do đó một khi trung bình được tìm thấy tất cả các yếu tố trong nửa trên đã được biết đến. – Accipitridae
Tôi sẽ đề xuất điều này:
Sử dụng Quicksort, chọn một số trục xoay. Điều này sẽ phân chia danh sách của bạn thành hai danh sách con, một nhỏ hơn so với danh sách con, một cái lớn hơn số đó. Nếu kích thước của danh sách con nhỏ hơn là < = N/2, hãy tính mức trung bình là a1.
Nếu size == N/2 or size == N/2 -1
bạn đã hoàn tất ngay lập tức.
Nếu không phân loại lại danh sách con lớn hơn cho đến khi tổng kích thước là N/2.
Nếu kích thước> phân vùng N/2, danh sách con nhỏ hơn.
Lặp lại tất cả cho đến khi hoàn thành.
P.S: bạn không cần phải sắp xếp.
Đó là 'O (n^2)' trong trường hợp xấu nhất ... –
Bạn có thể sử dụng hàng đợi ưu tiên. Chèn các phần tử vào hàng đợi duy trì số lượng các phần tử bạn đã xem, n. Giải nén n/2 các phần tử tối đa từ hàng đợi vào bộ tích lũy và tính giá trị trung bình.
Với cấu trúc dữ liệu được lựa chọn tốt phía sau hàng đợi, chẳng hạn như đống heap, điều này sẽ cung cấp cho bạn thời gian chạy là O(n log n), khi chèn là O(1) và trích xuất là O(log n).
Thật không may là thời gian chạy O (n) bạn đang tìm kiếm, nhưng với cấu trúc dữ liệu đã được triển khai, điều này sẽ tạo ra mã đơn giản dễ hiểu.
* Tìm * tối đa là O (1) trong vùng đệm Fibonacci, nhưng * loại bỏ * nó (do đó cho phép thứ hai đến tối đa được tìm thấy trong một O (1)) khác là O (log n). Nếu "insert" và "remove max" thực sự là cả O (1) trong một vùng Fibonacci, thì sẽ có thể sử dụng một để thực hiện một phép so sánh trong O (n). –
Bạn hoàn toàn đúng, xin lỗi, tôi đã chỉnh sửa câu trả lời của tôi cho phù hợp. Đó là nstn pstky thấp hơn ràng buộc về phân loại! –
Điều này rõ ràng là có thể giải được trong thời gian tuyến tính, nếu bạn có thể tìm thấy trung vị trong thời gian tuyến tính. Và việc tìm một trung vị trong thời gian tuyến tính là khó khăn, nhưng có thể. Xem ví dụ bài viết wikipedia trên selection algorithms.
Câu hỏi có liên quan đến lập trình (tức là giải quyết vấn đề này bằng chương trình) không? – BoltClock
Tôi donno. Bạn có thể cung cấp công thức toán học nếu bạn có phương pháp. Nó chỉ là một câu hỏi phỏng vấn. – Seeker
Đây là một trong những câu hỏi, nơi người phỏng vấn muốn biết liệu ứng cử viên có thể giảm các vấn đề thực tế về các thuật toán đã biết hay không. Điều này thường quan trọng hơn là có thể đọc thuộc lòng các thuật toán. Do đó, tôi có một thời gian khó khăn để hiểu lý do tại sao câu hỏi này đã được đóng cửa như là off-topic. – Accipitridae