题目描述

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。
例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

题解1:排序

代码

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
	sort(input.begin(), input.end());
	vector<int> v;
	for (int i = 0; i < k; i++) {
		v.push_back(input[i]);
	}
	return v;
}

题解2:大根堆

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。
在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

小根堆的定义：
priority_queue<int,vector,greater> small;
大根堆的定义：
priority_queue big;

代码

//小根堆的定义：  
// priority_queue<int,vector<int>,greater<int>> small;   
//大根堆的定义：  
//priority_queue<int> big;
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
	vector<int> v;
	if (input.size() == 0 || k == 0) return v;
	priority_queue<int> queue;
	for (int i = 0; i < input.size(); i++) {
		queue.push(input[i]);//大根堆中插入的元素会自动按照递增的顺序排序
		if (queue.size() > k)
			queue.pop();//弹出queue中最大元素
	}
	while (!queue.empty()) {
		v.push_back(queue.top());
		queue.pop();
	}
	return v;