每日一练：快排-最小k个数

面试题 17.14. 最小K个数 - 力扣（LeetCode）

题目要求：

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

快速排序 O(N)：

        快速排序可将数组分为3段：

        设区间1的长度为a，区间2的长度为b，区间c的长度为c；a、b、c与可能具有以下大小关系：

        （1）若a>k，则最小k个数在区间1中，以[sta,left]继续分割

        （2）若a+b>=k，则最小k个数包含区间1和区间2(部分或全部)，因为区间2中的元素都等于k，所以返回区间[sta,right-1]的前k个元素即可。

        （3）若a+b+c>=k，则最小k个数包含区间1、2和3(部分或全部)，此时可以先将区间1、2的所有元素保存起来，然后以[right,end]继续分割，但是只需要找前k-a-b个元素。

class Solution {
    vector<int> ret;

    vector<int> _smallestK(vector<int>& arr, int sta, int end, int k) {
        if (sta >= end)
            return ret;

        int key = arr[rand() % (end - sta + 1) + sta];
        int left = sta - 1, right = end + 1, cur = sta;
        while (cur < right) {
            if (arr[cur] == key)
                cur++;
            else if (arr[cur] < key)
                swap(arr[++left], arr[cur++]);
            else if (arr[cur] > key)
                swap(arr[--right], arr[cur]);
        }

        int a = left - sta + 1, c = end - right + 1,
            b = (end - sta + 1) - (a + c);
        if (a > k) {
            return _smallestK(arr, sta, left, k);
        } else if (a + b >= k) {
            for (int i = sta; i < sta + k; i++) {
                ret.push_back(arr[i]);
            }
            return ret;
        } else {
            for (int i = sta; i < sta + a + b; i++) {
                ret.push_back(arr[i]);
            }
            return _smallestK(arr, right, end, k - a - b);
        }
    }

public:
    vector<int> smallestK(vector<int>& arr, int k) {
        if (k == 0)
            return {};
        return _smallestK(arr, 0, arr.size() - 1, k);
    }
};

原文地址：https://blog.csdn.net/2303_78095330/article/details/144305741

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！