- Partition函数
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> result;
if(k<=0||input.size()==0||k>input.size()){
return result;
}
int begin=0;
int end=input.size()-1;
int index=Partition(input,begin,end);
while(index!=k-1){
if(index>k-1){
end=index-1;
index=Partition(input,begin,end);
}else{
begin=index+1;
index=Partition(input,begin,end);
}
}
for(int i=0;i<=index;i++){
result.push_back(input[i]);
}
return result;
}
private:
//和数组中超过一半的数不一样，要传地址，改变数组的数据
int Partition(vector<int>& numbers,int begin,int end){
if(begin>end){
return begin;
}
int key = numbers[begin];
while(begin<end){
while(begin<end&&numbers[end]>=key){
end--;
}
numbers[begin]=numbers[end];
while(begin<end&&numbers[begin]<=key){
begin++;
}
numbers[end]=numbers[begin];
}
numbers[begin]=key;
return begin;
}
};
- 容器适合处理海量数据(红黑树)
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(k<0||k>input.size()||input.size()==0){
return vector<int>();
}
multiset<int,greater<int>> res;
vector<int>::iterator cur;
for(cur=input.begin();cur!=input.end();cur++){
if(res.size()<k){
res.insert(*cur);
}else{
if(*cur<*(res.begin())){
res.erase(res.begin());
res.insert(*cur);
}
}
}
return vector<int>(res.begin(),res.end());
}
};
