这是在面试常遇到的topk问题。
题目描述：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
解题思路：
思路一：用快排对数组做一次排序，输出前k个。这种方法会改变原数组排列，复杂度为O(nlogn)。
思路二：基于partition思想，进行一次快速排序用哨兵数分割数组中的数据。由于partition每次将数组分成两段，左半部分小于关键字，右半部分大于关键字。可以递归做partition，关键字位置，若关键字位置等于k-1，则输出左半部分。否则，若大于k-1，则对左半部分做partition；若小于k-1，则往后拓展一位。
这种方法同样会改变原数组排列，算法复杂度为O(n)。
思路三：大顶二叉堆。基于红黑树（？？？）思想，首先创建一个大小为k的容器，用来存储最小的k个数字；然后每次从输入的n个整数中输入一个数，如果容器中已有的数字少于k个，则直接把读入的整数放入容器；如果容器中已有k个数字，则不能再插入新的数字而只能替换已有的数字。替换的原则：如果待插入的值m比容器中的最大值n小，则m替换n；如果待插入的值m比容器中的最大值n大，则保持不变。（在k个整数中找到最大值、删除容器最大值、插入一个新的数字）
可以用优先队列完成，设定一个大小为k的优先队列，将数组一次放进去，由于优先队列的排列是从大到小，所以每次当新的数进队时，当队列已满，就做出队操作，每次出队的都是最大的元素。因此最后保留在队列当中的就是最小的k个数。算法复杂度O(nlogk)，不会改变原数组的排列。该方法适合处理海量数据。
代码：
思路一：
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
if(input.size()== || k<)
return res;
if(input.size() < k)
return res;
sort(input.begin(), input.end());
for(int i=; i<k; i++)
res.push_back(input[i]);
return res;
}
};
思路二：
class Solution {
public:
int partition(vector<int>& a, int low, int high) //要改变vector，必须传入地址
{
int temp;
int base = low;
temp = a[low];
while(low<high)
{
while(a[high] >= temp && low<high)
high--;
while(a[low] <= temp && low<high)
low++;
if(low<high)
swap(a[low], a[high]);
}
swap(a[base], a[low]);
return low;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
if(input.size()== || k< || input.size() < k)
return res;
int low = ;
int high = input.size()-;
int index = partition(input, low, high);
while(index != (k-))
{
if(index > (k-))
{
high = index-;
index = partition(input, low, high);
}
else
{
low = index+;
index = partition(input, low, high);
}
}
for(int i=; i<k; i++)
res.push_back(input[i]);
return res;
}
};
思路三：
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
if(input.size()== || k< || input.size() < k)
return res;
priority_queue<int> q;
for(int i=; i<input.size(); i++)
{
q.push(input[i]);
if(q.size()>k)
{
q.pop();
}
}
while(!q.empty())
{
res.push_back(q.top());
q.pop();
}
return res;
}
};