最小的k个数

题目描述
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

思路
快速排序

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len=input.size();
        if(len==0 || k>len ||k<=0) 
            return vector<int>();
        if(len==k)
            return input;
        
        int start=0,end=len-1;
        int index=partition(input,start,end);
        while(index!=(k-1)){
            if(index>k-1){
                end=index-1;
                index=partition(input,start,end);
            }else{
                start=index+1;
                index=partition(input,start,end);
            }
        }
        vector<int> res(input.begin(),input.begin()+k);
        return res;
    }
    
    int partition(vector<int> &nums, int begin, int end){
        int low=begin, high=end;
        int pivot=nums[begin];
        while(low<high){
            while(low<high && nums[high]>=pivot)
                high--;
            if(low<high)
                nums[low++]=nums[high];
            while(low<high && nums[low]<=pivot)
                low++;
            if(low<high)
                nums[high--]=nums[low];
        }
        nums[low]=pivot;
        return low;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 最小的K个数 题目描述 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最...
    echoVic阅读 822评论 1 2
  • 寻找最小的 k 个数 题目描述: 输入 n 个整数,输出其中最小的 k 个。 分析和解法: 解法一:排序输出 要求...
    MinoyJet阅读 606评论 0 0
  • 解法一 最容易想到的方法是先对元素进行排序,然后取出前k个数,总时间复杂度O(n*logN)。你一定注意到了,当k...
    书呆子的复仇阅读 3,906评论 2 1
  • 问题:输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,...
    单倍体阅读 575评论 0 0
  • 题目描述输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1...
    quiterr阅读 257评论 0 0