嘛，这个思路，懂的都懂，就是调用标准库里边的sort函数直接排序然后返回前k个数字就行
class Solution {
public:
vector GetLeastNumbers_Solution(vector input, int k) {
vector res;
if(k==0 || input.size()(input.begin(), input.begin()+k);
}
};
方法二：堆排序
我们不是要一个最小的k个数么，那么我们用一个大顶堆也是很容易实现的
思路如下：
对每一个input中的元素进行如下操作：
1.当堆没有满时直接压入堆
2.当堆到达了k的size后，如果当前待处理元素小于大顶堆的堆顶，那么我们直接pop然后压入当前元素，否则什么也不做，这种方法的时间复杂度显然是O(nlogn)
class Solution {
public:
vector GetLeastNumbers_Solution(vector input, int k) {
vector res;
if(k==0 || input.size()> pq;
for(int x: input){
if(pq.size() x){
pq.pop();
pq.push(x);
}
}
}
while(!pq.empty()){
res.push_back(pq.top());
pq.pop();
}
return res;
}
};
方法三：快排思想
这里很巧妙啊，就是利用快排的partition返回的下标进行判断是否筛选出了K个最小的数。
partition在这里是个核心函数（和快排中一样）
思想就是：取一个数作为中心，然后利用这个中心将一个区间的数字划分为两部分，一部分小于，一部分大于这个中心。
然后就是上层的一个调用partition的函数，利用partition返回的下标来判断是否已经选出了最小的K个数：
1.下标等于k-1，说明已经完成
2.下标p小于k-1，说明需要在区间[p+1,r]继续快排
3.下标p大于k-1，说明取多了，在[l,p]之间快排
一定要注意这里是直接用下标判断的！！！
class Solution {
public:
int partition(vector &input, int l, int r){
int pivot=input[r-1];
//i记录的是比pivot大的元素的位置
//j是用来发现比pivot小的元素的位置
//走完后 i所在位置是右半部分第一个大于pivot的元素所在下标位置
//所以最后需要交换一下pivot和这个位置的元素
int i=l;
for(int j=i;j GetLeastNumbers_Solution(vector input, int k) {
vector res;
if(k==0 || k>input.size()){
return res;
}
int l=0, r=input.size();
while(l(input.begin(), input.begin()+k);
}else if(p+1
2.寻找第K大的数
方法一：快排
和上面的思路其实是一样的，不同的是这里是用个数来终止而不是下标。
代码如下所示：
class Solution {
public:
//常规的快排划分，但这次是大数在左
int partion(vector& a, int low, int high){
int temp = a[low];
while(low < high){
//小于标杆的在右
while(low < high && a[high] <= temp)
high--;
if(low == high)
break;
else
a[low] = a[high];
//大于标杆的在左
while(low < high && a[low] >= temp)
low++;
if(low == high)
break;
else
a[high] = a[low];
}
a[low] = temp;
return low;
}
int quickSort(vector& a, int low, int high, int K){
int p = partion(a, low, high);
if(K == p - low + 1)
return a[p];
else if(p - low + 1 > K)
return quickSort(a, low, p - 1, K);
else
return quickSort(a, p + 1, high, K - (p - low + 1));
}
int findKth(vector a, int n, int K) {
return quickSort(a, 0, n - 1, K);
}
};
方法二：堆
堆的方法也很好用：
直接用大顶堆如下所示：
class Solution {
public:
int findKth(vector a, int n, int K) {
priority_queue> pq;
int k=n-K+1;
for(int x: a){
if(pq.size() x){
pq.pop();
pq.push(x);
}
}
}
return pq.top();
}
};
在题解部分看到大佬直接手写小顶堆：
class Solution {
public:
int *heap;
int size = 0; // 初始化堆中元素个数为0
int findKth(vector a, int n, int K) {
heap = new int[K+5];
for (auto i : a) {
// 堆没满, 继续往堆里面放元素
if (size < K) {
add(i);
} else if (i > top()){
pop();
add(i);
}
}
return top();
}
// 增加一个元素
void add(int u) {
heap[++size] = u;
up(size); // 加到尾巴了, 需要向上调整
}
// 堆顶元素
int top() {
return heap[1];
}
void pop() {
heap[1] = heap[size--];
down(1); //向下调整
}
void up(int u) {
// 定义当前节点为cur, 父节点为f
int f = u / 2, cur = u;
// 如果有父节点且父节点更大, 说明需要往上调
while (f && heap[f] > heap[cur]){
swap(heap[f], heap[cur]);
up(f); // f也可能需要上调, 递归
}
}
void down(int u) {
// 定义u的左右儿子分别是lson和rson
int lson = u << 1, rson = u << 1 | 1;
// t表示父节点、左儿子、右儿子里面最小值的下标
int t = u;
// 如果左儿子未越界, 且更小, 则t=lson
if (lson <= size && heap[lson] < heap[t])
t = lson;
// 同上, 如果是大根堆这里就换一下
if (rson <= size && heap[rson] < heap[t] )
t = rson;
// 如果u不是t，说明三者中最小的是某个子节点，那就和最小的交换一下
if (u != t) {
swap(heap[u],heap[t]);
down(t); // 换过来之后的t, 有可能还需要继续向下
}
}
};
