题解 | #最小的K个数#
最小的K个数
http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
快排思想
class Solution {
public:
int partition(vector<int> &a, int left, int right){
int first = a[left];
while(left < right){
while(left < right && first <= a[right]){
right --;
}
if(first > a[right]){
a[left++] = a[right];
}
while(left <right && a[left] <= first){
left ++;
}
if(a[left] > first){
a[right--] = a[left];
}
}
a[left] = first;
return left;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
if(k == 0 || k > input.size()){
return res;
}
int left = 0, right = input.size()-1;
while(left < right){
int pos = partition(input, left, right);
if(pos == k-1){
break;
}else if(pos < k-1){
left = pos + 1;
}else{
right = pos - 1;
}
}
for(int i=0; i<k; i++){
res.push_back(input[i]);
}
return res;
}
}; 犯过两个错误： 1. 代码如下：
void quickSort(vector<int> &a, int left, int right, int k){
if(left >= right) return;
int pos = partition(a, left, right);
if (pos == k-1) return;
else if (pos > k-1) quickSort(a, left, pos-1, k);
else {
quickSort(a, left, pos-1, k);
quickSort(a, pos+1, right, k);
}
} 错误在于：如果pos落在k后，其前面的部分并不需要排序，如果代码这样写，实际运行时，一开始落在k右侧的pos在后面几轮是pos也会出现在k左侧。 为了避免这种情况，这里不应当将k带入递归当中
另外，可以化简res的输出：
if(pos == k-1){
return vector<int> ({input.begin(), input.begin()+k});
} 
基恩士成长空间 455人发布
