Làm thế nào để tìm k lân cận gần nhất với trung bình của n số khác biệt trong thời gian O (n)?

Question

Tôi có thể sử dụng thuật toán chọn trung vị của trung vị để tìm trung vị trong O (n). Ngoài ra, tôi biết rằng sau khi thuật toán được thực hiện, tất cả các phần tử bên trái của trung vị sẽ ít hơn là trung bình và tất cả các phần tử bên phải đều lớn hơn mức trung bình. Nhưng làm thế nào để tôi tìm thấy những người hàng xóm gần nhất với trung vị trong thời gian O (n)?

Nếu trung vị là n, các số ở bên trái nhỏ hơn n và các số ở bên phải lớn hơn n. Tuy nhiên, mảng không được sắp xếp ở bên trái hoặc bên phải. Các con số là bất kỳ tập hợp các số riêng biệt do người dùng đưa ra.

Vấn đề là từ Giới thiệu về thuật toán bởi Cormen, vấn đề 9.3-7

Answer 1

Thực ra, câu trả lời khá đơn giản. Tất cả những gì chúng ta cần làm là chọn các phần tử k với các khác biệt tuyệt đối nhỏ nhất từ ​​trung vị di chuyển từ m-1 đến 0 và m + 1 đến n-1 khi trung vị ở chỉ số m. Chúng tôi chọn các phần tử sử dụng cùng một ý tưởng chúng tôi sử dụng trong việc hợp nhất 2 mảng được sắp xếp.

Answer 2

Nếu bạn biết các chỉ số trung bình, mà chỉ nên ceil (array.length/2) có lẽ, sau đó nó chỉ nên được một quá trình liệt kê ra n (xk), n (x-k + 1), ..., n (x), n (x + 1), n ​​(x + 2), ... n (x + k) trong đó n là mảng, x là chỉ số của trung vị, và k là số hàng xóm bạn cần. (Có thể k/2, nếu bạn muốn tổng k, không phải k mỗi bên)

Answer 3

Đầu tiên chọn trung bình trong thời gian O(n), sử dụng standard algorithm mức độ phức tạp đó. Sau đó chạy lại danh sách, chọn các phần tử gần trung vị nhất (bằng cách lưu trữ các ứng cử viên nổi tiếng nhất và so sánh các giá trị mới với các ứng viên này, giống như tìm kiếm phần tử tối đa).

Trong mỗi bước của lần chạy bổ sung này thông qua danh sách các bước O (k) là cần thiết và vì k là hằng số, đây là O (1). Vì vậy, tổng thời gian cần thiết cho lần chạy bổ sung là O (n), cũng như tổng thời gian chạy của thuật toán đầy đủ.

Answer 4

Các trung vị của người trung bình có thể không giúp đỡ nhiều trong việc tìm kiếm các nước láng giềng gần nhất, ít nhất là cho lớn n. Đúng, bạn có mỗi cột của 5 phân vùng xung quanh nó trung bình, nhưng điều này là không đủ thông tin đặt hàng để giải quyết vấn đề.

tôi chỉ muốn điều trị trung bình như một kết quả trung gian, và đối xử với những người hàng xóm gần như một vấn đề ưu tiên hàng đợi ...

Một khi bạn có trung bình từ trung bình-of-trung vị, giữ một lưu ý của Giá trị của nó.

Chạy thuật toán heapify trên tất cả dữ liệu của bạn - xem Wikipedia - Binary Heap. So sánh, căn cứ vào kết quả về sự khác biệt liên quan đến giá trị trung vị đã lưu đó. Các mục ưu tiên cao nhất là những mục có giá trị ABS thấp nhất (giá trị trung bình). Điều này có O (n).

Mục đầu tiên trong mảng bây giờ là trung bình (hoặc bản sao của nó) và mảng có cấu trúc heap. Sử dụng thuật toán trích xuất heap để kéo ra nhiều hàng xóm gần nhất khi bạn cần. Đây là O (k log n) cho k lân cận gần nhất.

Miễn là k là hằng số, bạn nhận được O (n) trung bình của trung vị, O (n) heapify và O (log n) giải nén, cho O (n) tổng thể.

Answer 5

Bạn đã biết làm thế nào để tìm ra trung bình trong thời gian O (n)

nếu lệnh không quan trọng, lựa chọn các k nhỏ nhất có thể được thực hiện trong thời gian O (n) xin k nhỏ nhất đến RHS của trung bình và k lớn nhất để LHS của trung bình

from wikipedia

function findFirstK(list, left, right, k) 
if right > left 
    select pivotIndex between left and right 
    pivotNewIndex := partition(list, left, right, pivotIndex) 
    if pivotNewIndex > k // new condition 
     findFirstK(list, left, pivotNewIndex-1, k) 
    if pivotNewIndex < k 
     findFirstK(list, pivotNewIndex+1, right, k) 

đừng quên trường hợp đặc biệt, nếu k == n trở lại danh sách ban đầu

Answer 6

Bạn có thể sử dụng loại không so sánh, chẳng hạn như sắp xếp radix, trên danh sách số L, sau đó tìm k hàng xóm gần nhất bằng cách xem xét các cửa sổ của phần tử k và kiểm tra các điểm cuối cửa sổ. Một cách khác để nói "tìm cửa sổ" là tìm tôi giảm thiểu số abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i] - L[n/2]) (nếu k là lẻ) hoặc abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i+1] - L[n/2]) (nếu k là chẵn). Kết hợp các trường hợp, abs(L[(n-k)/2+i] - L[n/2]) + abs(L[(n+k)/2+i+!(k&1)] - L[n/2]). Một cách đơn giản, O (k) của việc tìm kiếm tối thiểu là bắt đầu với i = 0, sau đó trượt sang trái hoặc phải, nhưng bạn sẽ có thể tìm mức tối thiểu trong O (log (k)).

Biểu thức bạn thu nhỏ xuất phát từ việc chuyển đổi L sang danh sách khác, M, bằng cách lấy sự khác biệt của từng phần tử từ trung vị.

m=L[n/2] 
M=abs(L-m) 

i giảm thiểu M[n/2-k/2+i] + M[n/2+k/2+i].

Answer 7

Vì tất cả các phần tử đều khác nhau, có thể có tối đa 2 phần tử có cùng sự khác biệt so với giá trị trung bình. Tôi nghĩ rằng tôi dễ dàng có 2 mảng A [k] và B [k] chỉ số đại diện cho giá trị tuyệt đối của sự khác biệt so với giá trị trung bình. Bây giờ nhiệm vụ là chỉ cần điền các mảng và chọn các phần tử k bằng cách đọc các giá trị k không trống đầu tiên của các mảng đọc A [i] và B [i] trước A [i + 1] và B [i + 1]. Điều này có thể được thực hiện trong thời gian O (n).

Answer 8

med=Select(A,1,n,n/2) //finds the median 

for i=1 to n 
    B[i]=mod(A[i]-med) 

q=Select(B,1,n,k) //get the kth smallest difference 

j=0 
for i=1 to n 
    if B[i]<=q 
    C[j]=A[i] //A[i], the real value should be assigned instead of B[i] which is only the difference between A[i] and median. 
     j++ 
return C 

Answer 9

Không ai có vẻ hoàn toàn có điều này. Đây là cách để làm điều đó. Đầu tiên, hãy tìm trung vị như mô tả ở trên. Đây là O (n). Bây giờ đỗ dấu trung bình ở cuối mảng, và trừ trung bình khỏi mọi phần tử khác. Bây giờ tìm phần tử k của mảng (không bao gồm phần tử cuối cùng), sử dụng lại thuật toán chọn nhanh. Điều này không chỉ tìm thấy phần tử k (theo thứ tự), nó cũng rời khỏi mảng sao cho số k thấp nhất nằm ở đầu mảng. Đây là những k gần gũi nhất với mức trung bình, một khi bạn thêm trung bình trở lại trong

Answer 10

Bạn có thể giải quyết vấn đề của bạn như thế:.

Bạn có thể tìm ra trung bình trong thời gian O (n), w.g. sử dụng thuật toán O (n) nth_element.

Bạn lặp qua tất cả các yếu tố substutiting mỗi với một cặp:

the absolute difference to the median, element's value. 

Một lần nữa bạn nth_element với n = k. sau khi áp dụng thuật toán này, bạn được đảm bảo có k yếu tố nhỏ nhất trong sự khác biệt tuyệt đối đầu tiên trong mảng mới. Bạn lấy chỉ mục của họ và XONG!