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

Question

我必须在一个 const 向量中找到 4 个最大的数字和 return 它们的位置。我希望此代码具有最佳时间和 space 复杂性。我的第一个想法是将这个 const vector 复制到 vector 中并对其进行 4 次冒泡排序。这给了我 4*N 但我必须创建一个向量。第二个想法是将此 const 向量中的所有内容放入 priority_queue。这给了我一个 N*log2(N) 时间复杂度而不创建另一个变量。 N的最大值在100左右。

是否有任何其他选项可以以最快且 space 消耗最少的方式完成此操作？

编辑：哪个最大并不重要，我只需要 return 这 4 个项目在输入向量中的位置。

Answer 1

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

循环 const 向量的剩余项，如果当前值 > 最小值，则替换它并重新排序 4 元素向量

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 的堆。然后你遍历向量并相应地更新堆。

示例代码使用标准堆方法并找到 最小值 值 (from here) 如下。

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;

相应调整：

在堆中使用一对索引，值来跟踪您喜欢的位置return
使用比较器比较对中的值并建立描述。排序

如果您的号码 n 将来可能 change/grow，这比 @Jugal Rawlani 的解决方案更通用。否则他的想法获胜。

Answer 4

您可以使用额外的 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; });

这是一个 demo。

请注意，此解决方案使用 O(n) 额外的 space。如果 N 变大，那么这可能不是仅查找 4 最大元素的正确方法。如果你想要 M 最大的元素，它仍然是一个很好的方法，其中 M 像 N.

一样增长

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

Most efficient way to find iterators of 4 maximum values in const vector in C++

c++

complexity-theory

constants

vector