剑指offer29_topK问题快排方式解决

是三水不是泗水

于 2020-08-25 14:11:37 发布

阅读量153

点赞数

分类专栏： C++/PAT/洛谷OJ

本文链接：https://blog.csdn.net/csg3140100993/article/details/108220061

版权

C++/PAT/洛谷OJ 专栏收录该内容

257 篇文章

订阅专栏

本文介绍了一种寻找数组中最小K个数的算法实现，通过快速排序的partition函数进行分区，递归地找到第K小元素的位置，最终返回前K个最小元素的列表。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述

输入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) {
        vector<int> res;
        if(input.size()<=0) return res;
        int index=topk(input,0,input.size()-1,k);
        for(int i=0;i<=index;i++){//记得带上等号
            res.push_back(input[i]);
        }
        return res;
    }
    int partion(vector<int> &a,int left,int right){//快排的partition函数
        int temp=a[left];
        while(left<right){
            while(left<right&&a[right]>temp) right--;
            a[left]=a[right];
            while(left<right&&a[left]<=temp) left++;
            a[right]=a[left];
        }
        a[left]=temp;
        return left;
    }
    int topk(vector<int> &a,int left, int right, int k){//寻找topk的位置
        int index = -1;
        if(left <= right){//考虑特殊情况带上等号
            int pos = partion(a,left,right);
            int len = pos-left+1;
            if(len == k)
                index = pos;
            else if (len < k){
                index = topk(a,pos+1,right,k-len);
            }else {
                index = topk(a,left,pos-1,k);
            }
        }
        return index;
    }
};