在C++中用const向量寻找4个最大值的迭代器的最有效方法

Question

我必须在一个const向量中找到4个最大的数字并返回它们的位置。我希望这段代码有最好的时间和空间复杂度。我的第一个想法是把这个const向量复制到向量中，然后进行4次气泡排序。这样我就得到了4*N，但我必须创建一个向量。第二个想法是把这个const vector中的所有东西放到priority_queue中。这给了我一个N*log2(N)的时间复杂度，而不需要再创建一个变量。N的最大值是100左右。

有没有其他方案可以用最快、最不占空间的方式来做？

EDIT: 哪一个是最大的并不重要，我只需要返回这4个项目在输入向量中的位置。

Answer 1

你可以通过一个额外的 vector和 nth_element 算法，它是 O(n) 时候。

std::vector<int> const v = ...;

// create a vector of elements with original indexes
std::vector<std::pair<int,int>> res;

// populate the result vector
int k = 0;
for (int i : v)
  res.push_back({i,k++});

// find the maximum 4 elements
std::nth_element(res.begin(), res.begin() + 4, res.end(),
   [](auto const &a, auto const &b) { return a.first > b.first; });

这里有一个 演示.

请注意，这个解决方案使用的是 O(n) 额外的空间。如果 N 增长，那么这可能不是正确的方法，以找到只是 4 最大的元素。如果你想得到的是 M 最大的元素，其中 M 长势喜人 N.

Answer 2

O(n)解决方案

std::vector<int>::iterator max1 = v.begin(), max2 = v.begin(), max3 = v.begin(), max4 = v.begin();
for(std::vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    if((*max1) < (*it)) {
        max4 = max3;
        max3 = max2;
        max2 = max1;
        max1 = it;
    } else if((*max2) < (*it)) {
        max4 = max3;
        max3 = max2;
        max2 = it;
    } else if((*max3) < (*it)) {
        max4 = max3;
        max3 = it;
    } else if((*max4) < (*it)) {
        max4 = it;
    }
}    

Answer 3

是的，使用 堆 的大小为4。然后在向量中迭代并相应地更新堆。

使用std堆方法和查找的示例代码。最低 值 (从此)以下。

const std::vector<int> input;
const size_t n = 4;
std::vector<int> ret(n);
auto dfirst = ret.begin(), dlast = ret.end();

// initialize heap with infinity distances
std::fill(dfirst, dlast, 100000000000); // do better here

for (auto it = input.begin(); it != input.end(); ++it)
{
    if (*it < *dfirst) {
        // remove max. value in heap
        std::pop_heap(dfirst, dlast); // add comparator as third arg

        // max element is now on position "back" and should be popped
        // instead we overwrite it directly with the new element
        *(dlast-1) = *it;
        std::push_heap(dfirst, dlast); // add comparator as third arg
    }
}
std::sort_heap(dfirst, dlast); // remove if not needed, or add comparator as third arg
return ret;

据此进行调整。

• 在堆中使用一对index, value来跟踪你想返回的位置。
• 使用比较器，在对中的值上进行比较，并建立一个降序。

这比@Jugal Rawlani的解决方案更通用，如果你的号。n 未来可能会改变增长。否则他的想法就赢了。

Answer 4

将4个第一元素读入一个4元素向量中，对这个向量进行排序，使4个元素中的最小值在索引0中。

在const向量的剩余项上循环，如果当前值> min，替换它，并重新对4元素向量进行排序。