việc tìm kiếm các trung bình của 5 yếu tố

Question

những câu dưới đây đã được hỏi trong một cuộc phỏng vấn gần đây microsoft

Với một mảng không được phân loại kích thước 5. bao nhiêu so sánh tối thiểu là cần thiết để tìm ra trung bình? sau đó ông mở rộng nó cho kích thước n.

giải pháp cho 5 yếu tố theo tôi là 6

1) use 3 comparisons to arrange elements in array such that a[1]<a[2] , a[4]<a[5] and a[1]<a[4] 
a) compare a[1] and a[2] and swap if necessary 
b) compare a[4] and a[5] and swap if necessary 
c) compare a[1] and a[4].if a[4] is smaller than a[1] , then swap a[1] wid a[4] and a[2] wid a[5] 
2)if a[3]>a[2].if a[2]<a[4] median value = min(a[3],a[4]) else median value=min(a[2],a[5]) 
3)if a[3]<a[2].if a[3]>a[4] median value = min(a[3],a[5]) else median value=min(a[2],a[4]) 

này có thể được mở rộng đến các yếu tố n. nếu không làm thế nào chúng ta có thể tìm thấy trung vị trong các phần tử n trong O (n) ngoài việc chọn nhanh

Answer 1

Thuật toán chọn chia danh sách thành các nhóm gồm năm phần tử. Sau đó, đối với mỗi nhóm năm, trung bình được tính toán (một hoạt động có khả năng có thể được thực hiện rất nhanh nếu năm giá trị có thể được nạp vào sổ đăng ký và so sánh - 6 so sánh min). Chọn sau đó được gọi là đệ quy trên danh sách con này của n/5 yếu tố để tìm trung bình thực sự của chúng.