剑指offer - 最小的K个数

墨蓝 2022-09-25 01:28 73阅读 0赞

class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
        {
            vector<int> res;
            if(input.empty()||input.size()<k||k<=0)
                return res;
            int low=0,high=input.size()-1,mid=-1;
            while(mid!=(k-1))
            {
                if(mid>(k-1))
                    high=mid-1;
                else
                    low=mid+1;
                mid=Partition(input,low,high);
            }
            for(int i=0;i<=mid;i++)
                res.push_back(input[i]);
            return res;
        }
        int Partition(vector<int> &n,int low,int high)
        {
            int key=n[low];
            while(low<high)
            {
                while(low<high&&key<=n[high])
                    high--;
                n[low]=n[high];
                while(low<high&&key>=n[low])
                    low++;
                n[high]=n[low];
            }
            n[low]=key;
            return low;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，73人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer - 最小的K个数

class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int

墨蓝/ 2022年09月25日 01:28/ 0 赞/ 74 阅读

相关剑指Offer 最小的K个数

题目描述: 输入n个整数，找出其中最小的k个数思路: 首先想到的是对数组进行按从小到大排序然后再选出最小的前K个数。排序算法里选择排序是每次排序都可以确定数组在最后排好

骑猪看日落/ 2022年06月10日 12:14/ 0 赞/ 201 阅读

相关剑指offer 最小的k个数

1.题目描述输入n个数字，找出其中最小的k个数。注：有的还会要求保持原有的顺序输出 2.分析两种思路： 1）利用快排的思想，找到第k大的分界点。左边的

男娘i/ 2022年06月08日 09:38/ 0 赞/ 161 阅读

相关剑指Offer:最小的k个数

题目：输入N个整数，找出其中最小的k个数。例如，输入4,5,1,6,2,7,3,8. 最小的4个数字是1,2,3,4. 思路：就是把那个容器只能存k个数，当容器未满时，直

骑猪看日落/ 2022年04月25日 03:08/ 0 赞/ 186 阅读

相关【剑指offer】最小的k个数

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

「爱情、让人受尽委屈。」/ 2022年04月10日 12:39/ 0 赞/ 195 阅读

相关剑指offer:最小的k个数

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

以你之姓@/ 2022年04月10日 08:58/ 0 赞/ 213 阅读

相关剑指offer:最小的k个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。思路：使用C++中的mutis

电玩女神/ 2022年02月26日 19:48/ 0 赞/ 198 阅读

相关剑指Offer-最小的K个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。解题思路—快排：时间复杂度O(nl

Dear 丶/ 2022年02月21日 16:54/ 0 赞/ 242 阅读

相关 [剑指offer]最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。最大堆时间复杂度O（nlogk）

ゞ浴缸里的玫瑰/ 2021年12月19日 22:29/ 0 赞/ 249 阅读

相关剑指offer：最小的K个数

试题：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。代码：使用有序结构存储这k个数就可以

旧城等待，/ 2021年06月24日 16:09/ 0 赞/ 364 阅读