下面我们讨论上述问题的解决思路：
- 思路一
如果采用堆排序的构造最小堆，然后每次输出根结点元素后再调整最小堆然后反复调整k次。时间复杂度分析：初始化最小堆所需要的时间复杂度就是o(n)，然后需要经过K次调整，每次调整的时间复杂度为o(lgn),因此时间复杂度为o(n+klogn)。- 思路二
还是采用堆的思想，现在我们采用最大堆的思想。首先将数组前k个数放入优先队列中(就是建立最大堆)，然后遍历剩下的数，若该数小于堆头的数，这说明堆头的数至少大于K个数,因此弹出，把该数插入到堆中。若该数大于堆头的数，这说明，该数也至少大于K个数，直接忽略。遍历下一个数。遍历完成之后，堆中保存的是最小的K个数。实际复杂度分析：初始建立最大堆得时间复杂度为o(k),然后遍历剩下的数，调整的时间复杂度为o(nlogk),总的时间复杂度为o(k+nlogk)，代码如下：
vector<int> Getknumber(vector<int> input, int k)
{
vector<int> num;
int len = input.size();
if (k <= 0 || k > len)
return num;
priority_queue<int, vector<int>, less<int>>s;//
for (int i = 0; i < len; i++)
{
if (s.size() != k)
{
s.push(input[i]);
}
else if (s.top()> input[i]) {
s.pop();
s.push(input[i]);
}
}
for (int i = 0; i < k; i++)
{
num.push_back(s.top());
s.pop();
}
return num;
}
