时间戳

首页 > 解决方案 > 在未排序的数组中查找最小/最大 K 元素的最有效算法是什么？

c++ - 在未排序的数组中查找最小/最大 K 元素的最有效算法是什么？

问题描述

我有一个未排序的 N 个元素的向量，并且想找到 K 个最小或最大的元素。K 预计为 K << N 远小于 N，但算法应该是稳健的，以便对于较大的 K 值也有效，例如 N 的 50-80%。

沿着重用快速排序的思路思考意味着使用第 K 个最小/最大元素作为分区的枢轴。但是找到第 K 个最小/最大值已经在计算 OP 的解决方案。

这是快速排序的分区位：

template<typename T>
int partition(std::vector<T>& arr, int low, int high, T pivot) {
    int i = (low - 1); 

    for (int j = low; j <= high - 1; ++j) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

如果我知道该pivot值对应于第 K 个最小/最大的值，那么我可以使用上面的分区来解决我的 OP。

标签： c++algorithm

解决方案

Partial_sort会将最少（最多）的 K 个元素放在一个容器的前面，并对它们进行排序。像这样称呼它

std::partial_sort(arr.begin(), arr.begin() + K, arr.end());
std::partial_sort(arr.begin(), arr.begin() + K, arr.end(), std::greater<>());

它将运行大约 N log K 时间

推荐阅读