選擇算法問題

Question

假設您有一個包含n個項目的數組A，並且您希望找到A項中最接近的 中的k個項目。例如，如果A包含9個值{7,14,10， 12,2,11,29,3,4} 和k = 5，那麼答案將是值{7,14,10,12,11}，因爲中位數爲012，並且這些是A最接近10.給出一個算法 來解決O（n）時間中的這個問題。我知道一個選擇算法（深度選擇）是這個問題的適當算法，但我認爲這將運行在O（n * logn）時間而不是O（n）。任何幫助將不勝感激:)

Answer 1

首先你需要找到位數，可以在O(n)（使用霍爾的Quickselect算法爲例）來完成。

然後，您將需要實現一種排序算法，根據它們與中值的絕對距離（最小距離優先）排列陣列中的元素。

如果要以這種方式對整個陣列進行排序，取決於所使用的算法，這通常需要從O(n * log n)到O(n^2)之間的某個位置。但是，由於您只需要第一個值k，因此複雜度可以降至O(k * log n)至O(k * n)。

由於k是一個常數，不依賴於所述陣列的大小，在最壞的情況下的總體複雜性將是：O(n)（用於找到中值）+ O(k * n)（分選），這是O(n)整體。

Answer 2

我想你可以在quicksort上使用一個變體。

您從n件物品的集合S開始，正在尋找「中等」k物品。你可以把這看作是將S分成n-k/2（「下」項），k（「中」項）和n-k/2（「上」項）三部分。

這給了我們一個策略：首先從S中刪除較低的n - k/2項，離開S'。然後取出高位n - K從S/2項」，留下S‘’，這是S.

中間k個項目

可以這種方式使用‘半快速排序’容易分割的一組：選擇一個樞軸，將這個集合分成L和U（上下兩個元素與關鍵點對應），那麼你知道分區中要丟棄的項目必須是L的全部或U的一部分，反之亦然：相應的遞歸。

[進一步思考，這可能不是你想要什麼，如果你定義「最接近平均」，在一些其他的方式，但它是一個開始。]

Answer 3

假設：我們關心A中的k值這是最接近的中位數。如果我們有一個A = {1,2,2,2,2,2,2,2,2,2,2,2,2,3}，並且k = 3，那麼答案是{2,2,2}。同樣，如果我們有A = {0,1,2,3,3,4,5,6}和k = 3，則答案{2,3,3}和{3,3,4}同樣有效。此外，我們對這些值來自哪些指數不感興趣，但我想對算法進行一些小的調整就可以。

1. 作爲Grodrigues狀態，首先找到在O（n）的時間中位數。當我們在這裏，跟蹤最大和最小數字
2. 接下來，創建一個數組K，k個項目long。該數組將包含項目距中位數的距離。（請注意，
3. 將A的前k項複製到K中。
4. 對於每個項A [i]，比較A [i]從中值到K的每個項的距離。如果A [i]是作爲一種優化，我們也可以跟蹤K的距離中位數最近和最遠的項目，所以我們有一個比K更快的比較，或者我們可以保持K個排序，但是沒有優化是必要的，O（n）的時間來操作

僞代碼，C++ ISH：

 
/* n = length of array 
* array = A, given in the problem 
* result is a pre-allocated array where the result will be placed 
* k is the length of result 
* 
* returns 
* 0 for success 
* -1 for invalid input 
* 1 for other errors 
* 
* Implementation note: optimizations are skipped. 
*/ 
#define SUCCESS  0 
#define INVALID_INPUT -1 
#define ERROR   1 
void find_k_closest(int n, int[] array, int k, int[] result) 
{ 
    // if we're looking for more results than possible, 
    // it's impossible to give a valid result. 
    if(k > n) return INVALID_INPUT; 


    // populate result with the first k elements of array. 
    for(int i=0; i<k; i++) 
    { 
    result[i] = array[i]; 
    } 

    // if we're looking for n items of an n length array, 
    // we don't need to do any comparisons 
    // Up to this point, function is O(k). Worst case, k==n, 
    // and we're O(n) 
    if(k==n) return 0; 

    // Assume an O(n) median function 
    // Note that we don't bother finding the median if there's an 
    // error or if the output is the input. 
    int median = median(array); 

    // Convert the result array to be distance, not 
    // actual numbers 
    for(int i=0; i<k; i++) 
    { 
    result[i] = result[i]-median; 
     // if array[i]=1, median=3, array[i] will be set to 2. 
     //    4   3       -1. 
    } 

    // Up to this point, function is O(2k+n) = O(n) 


    // find the closest items. 
    // Outer loop is O(n * order_inner_loop) 
    // Inner loop is O(k) 
    // Thus outer loop is O(2k*n) = O(n) 
    // Note that we start at k, since the first k elements 
    // of array are already in result. 
    OUTER: for(int i=k; i<n; i++) 
    { 
    int distance = array[i]-median; 
    int abs_distance = abs(distance); 

    // find the result farthest from the median 
    int idx = 0; 
#define FURTHER(a,b) ((abs(a)>abs(b)) ? 1 : 0; 
    INNER: for(int i=1; i<k; i++) 
    { 
     idx = (FURTHER(result[i],result[i-1])) ? i:i-1; 
    } 

    // If array[i] is closer to the median than the farthest element of 
    // result, replace the farthest element of result with array[i] 
    if(abs_distance < result[idx]){ result[idx] = distance; } 
    } 
    } 
    // Up to this point, function is O(2n) 

    // convert result from distance to values 
    for(int i=0; i<k; i++) 
    { 
    result[i] = median - result[i]; 
     // if array[i]=2 , median=3, array[i] will be set to 1. 
     //    -1   3       4. 
    } 
}