在兩個向量中選擇n個最大的元素

Question

我有兩個向量，每個包含n個未分類的元素，我怎樣才能在這兩個向量中獲得n個最大的元素？

我的解決方案是將兩個向量合併成一個具有2n個元素的向量，然後使用std::nth_element算法，但是我發現效率不高，所以任何人都有更高效的解決方案。萬分感激。

Answer 1

您可以將元素推入priority_queue，然後彈出n元素。

Answer 2

假設n遠小於N，這是非常有效的。獲得minElem很便宜，以L比如果n < < N.兩個向量的排序

L := SortedList() 
For Each element in any of the vectors do 
{ 
    minElem := smallest element in L 
    if(element >= minElem or if size of L < n) 
    { 
    add element to L 
    if(size of L > n) 
    { 
     remove smallest element from L 
    } 
    } 
} 

Answer 3

vector<T> heap; 
heap.reserve(n + 1); 

vector<T>::iterator left = leftVec.begin(), right = rightVec.begin(); 

for (int i = 0; i < n; i++) { 
    if (left != leftVec.end()) heap.push_back(*left++); 
    else if (right != rightVec.end()) heap.push_back(*right++); 
} 

if (left == leftVec.end() && right == rightVec.end()) return heap; 

make_heap(heap.begin(), heap.end(), greater<T>()); 

while (left != leftVec.end()) { 
    heap.push_back(*left++); 
    push_heap(heap.begin(), heap.end(), greater<T>()); 
    pop_heap(heap.begin(), heap.end(), greater<T>()); 
    heap.pop_back(); 
} 

/* ... repeat for right ... */ 

return heap; 

注意我用* _heap，而不是直接priority_queue因爲priority_queue並沒有其底層提供接入便宜插入排序數據結構。這是O（N log n），比原始O（N log N）方法稍好一些，如果n < < N

Answer 4

您可以在兩個矢量的概念上並行執行「n元素」算法很簡單（至少這個簡單的變體在平均情況下只是線性的）。

1. 挑選一個關鍵點。
2. 分區（標準::分區）通過該樞軸的兩個向量。你將有第一個向量由一些排序爲i的元素分割，第二個向量由排序爲j的某個元素分割。我在這裏假設降序。
3. 如果i + j < n，則在右側爲n-i-j最大元素遞歸。如果i + j> n，則在左側遞歸n個最大的元素。如果你擊中i + j == n，則停止遞歸。

你基本上只需要確保在每一步中通過相同的樞軸分區兩個向量。給定一個不錯的支點選擇，這個算法在平均情況下是線性的（並且在原地工作）。

參見：http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm

編輯：（希望）澄清的算法的位。