求问关于k个最小元素

quick select是O(n)但好像edge case很多，求问其他方法。

找到前k小（大）的和找第k小是等价的。因为有了第k小（大）元素x后，你可以O(n) scan一下整个数组找到所有比x小（大）的元素就行了。

你是要找“最小的k个元素”还是“第k个最小元素”？

stellari 发表于 2016-10-24 02:57
你是要找“最小的k个元素”还是“第k个最小元素”？

最小的k个

kingiori1 发表于 2016-10-24 06:54
最小的k个

Quickstart是最佳方法。而且实现起来并不难，和quicksort差不多。其他方法比如用heap之类的只能达到O(nlogk)的复杂度。我觉得你还是认真地看一下quickselect的实现比较好。其实并没有什么edge case需要额外处理，唯一的问题是在partition的时候可能要需要弄清swap的规则，这时可能涉及到许多case，但是这些case可以用一段简单的代码涵盖之。网上应该有不少quickselect的实现，你不妨查阅一下。

refer to nth_element in <algorithm>

楼主可以去参考lc 215的第二高票回答，求最小只不过是把几个大于小于换过来

今天刚看quick select，没有edge case的，implement也不难，我来复制粘贴也算记录一下：

因为求k个最小和第k个最小是同样的：

我们可以使用分而治之的方法来解决这一问题。如果将全部元素划分为两个子序列A和B,使得A中的全部元素都小于等于B中的任何元素,我们就可按照下面的方法减小问题的规模:

1. 比较子序列A的长度和k的大小;

2. 若k <= |A|,则第k小的元素必然在A中,我们可以丢弃子序列B,然后在A中进一步查找;
3. 若|A| < k,则第k小的元素必然在B中,我们可以丢弃子序列A,然后在B中进一步查找第(k − |A|)小的元素。

注意下划线部分强调了递归的特性。理想情况下,我们总是将序列划分为相 等长度的两个子序列A和B,这样每次都将问题的规模减半,因此性能为线性时 间O(n)。


关键问题是如何实现划分,将前m小的元素放入一个子序列中,将剩余元素放入另一个中。
回忆快速排序中的划分算法,它将所有小于pivot的元素移动到前面,将大于pivot的元素移动到后面。根据这一思路,我们可以构造一个分而治之的k选 择算法,称为“快速选择算法”。


1. 随机选择一个元素(例如第一个)作为pivot;

2. 将所有不大于pivot的元素放入子序列A;将剩余元素放入子序列B;

3. 比较A的长度和k,若|A| = k − 1,则pivot就是第k小的元素;

4. 若|A| > k − 1,递归在A中寻找第k小的元素;

5. 否则,递归在B中寻找第(k − 1 − |A|)小的元素;

我觉得这个讲的很清楚，摘自<初等算法>.

然后Quickselect也写的蛮好， implement 也不难

写一个partition函数和select函数，这里有很多代码可供参考  https://rosettacode.org/wiki/Quickselect_algorithm

quickselect 没什么corner case啊 这是找第k大的代码 找到这个把前k个输出出来就是前k大的了

class Solution {
public:
    int helper(vector<int>& nums, int start, int end, int k) {
        if(end <= start)
            return nums[start];
        int idx = start;
        for(int i = start; i <= end; i++) {
            if(nums[i] <= nums[end]){
                swap(nums[i], nums[idx]);
                idx++;
            }
            idx--;
        }
        if(idx == k)
            return nums[idx];
    }
    int findKthLargest(vector<int>& nums, int k) {
        return helper(nums, 0, nums.size(), k - 1);
    }
};

quickselect 是estimate case O(n)，不是worst case O(n)，要worst case O(n)右转median of median