c++ - 获取 vector 中 k 个最大值的索引的有效方法

Question

如何创建 std::map<int, float>来自vector<float> ，因此映射包含 vector 中的 k 个最大值，键是 vector 中值的索引。

一种天真的方法是遍历 vector (O(n))，提取并删除 (O(n)) 最高元素 k 次 (O(k))，导致复杂度为 O(k*n ^2)，我猜这是次优的。

更好的方法是只复制 (O(n)) 并删除最小的直到大小为 k。这将导致 O(n^2)。还是多项式...

有什么想法吗？

Answer 1

下面应该做的工作:

#include <cstdint>
#include <algorithm>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>

// Compare: greater T2 first.
struct greater_by_second
{
    template <typename T1, typename T2>
    bool operator () (const std::pair<T1, T2>& lhs, const std::pair<T1, T2>& rhs)
    {
        return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first);
    }
};


std::map<std::size_t, float> get_index_pairs(const std::vector<float>& v, int k)
{
    std::vector<std::pair<std::size_t, float>> indexed_floats;

    indexed_floats.reserve(v.size());
    for (std::size_t i = 0, size = v.size(); i != size; ++i) {
        indexed_floats.emplace_back(i, v[i]);
    }
    std::nth_element(indexed_floats.begin(),
                     indexed_floats.begin() + k,
                     indexed_floats.end(), greater_by_second());
    return std::map<std::size_t, float>(indexed_floats.begin(), indexed_floats.begin() + k);
}

让我们测试一下:

int main(int argc, char *argv[])
{
    const std::vector<float> fs {45.67f, 12.34f, 67.8f, 4.2f, 123.4f};

    for (const auto& elem : get_index_pairs(fs, 2)) {
        std::cout << elem.first << " " << elem.second << std::endl;
    }
    return 0;
}

输出:

2 67.8
4 123.4