在两个向量中选择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

编辑：（希望）澄清的算法的位。