【算法】C++算法求数组中最小的K个数

输入n个整数&＃xff0c;找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字&＃xff0c;则最小的4个数字是1,2,3,4。

解法一&＃xff1a;排序后&＃xff0c;取出前k个数。O(nlogn)。

代码略。

解法二&＃xff1a;建立n个元素的最小堆&＃xff0c;每次去除堆顶的最小值&＃xff0c;然后弹出堆顶&＃xff0c;重新构成最小堆。

O(klogn)

class Solution
{
public:vector GetLeastNumbers_Solution(vector input, int k){vector ret;if (input.empty() || k > input.size())return ret;make_heap(input.begin(), input.end(), greater());for (int i &＃61; 0; i ());ret.push_back(input.back());input.pop_back();}return ret;}
};

解法三&＃xff1a;建立k个元素的最大堆(借助multiset来完成)&＃xff0c;遍历数组&＃xff0c; &＃xff08;整个堆只有k个单元&＃xff09;

1、如果堆没有k个元素 或者 当前数组元素比堆顶小&＃xff0c;那就把堆顶弹出&＃xff0c;当前元素压入&＃xff0c;重新构成堆

2、否则&＃xff0c;遍历数组下一个元素

最后堆中的元素就是最小的k个数。

O(nlogk) 适合海量数据

class Solution {
public:vector GetLeastNumbers_Solution(vector input, int k){vector ret;if (input.empty() || k > input.size())return ret;for (int i &＃61; 0; i ());for (int i &＃61; k; i ());ret.pop_back();ret.push_back(input[i]);push_heap(ret.begin(), ret.end(), less());}}return ret;}
};

解法三&＃xff1a;快排变种&＃xff0c;每次遍历将数组分为两边。

O(n)

class Solution {
public:vector GetLeastNumbers_Solution(vector input, int k){if (input.empty() || k > input.size())return input;int start &＃61; 0, end &＃61; input.size() - 1;while (start k - 1)end &＃61; index;elsebreak;}return vector (input.begin(), input.begin() &＃43; k);}int Partition(vector& input, int start, int end){if (start >&＃61; end) return start;int i &＃61; start, j &＃61; end;int pivot &＃61; input[(end - start) / 2 &＃43; start];while (i <&＃61; j){while (i <&＃61; j && input[j] > pivot)j--;while (i <&＃61; j && input[i] &＃61; start)? j : start;}
};