讨论/题目交流/面试题 17.14. 最小K个数 这题用快排找前 arr[0,k-1],为什么以arr[k]分界。emmm/
面试题 17.14. 最小K个数 这题用快排找前 arr[0,k-1],为什么以arr[k]分界。emmm

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。
输入: arr = [1,3,5,7,2,4,6,8], k = 4
输出: [1,2,3,4]

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        int left = 0, right = arr.size() -1;
        while(left != k) {
            int pivot = arr[left];
            int low = left, high = right;
            while(low < high) {
                while(low < high && arr[high] >= pivot)
                    --high;
                arr[low] = arr[high];
                while(low < high && arr[low] <= pivot)
                    ++low;
                arr[high] = arr[low];
            }
            arr[low] = pivot;
            if(low == k)
                left = low;
            else if(low > k)
                right = low - 1;
            else
                left = low + 1;
        }
        return  vector<int>(arr.begin(),arr.begin() + k);
    }
};
展开讨论
hayami🌸发起于 2020-05-11
最近编辑于 2020-05-11

晕了。╥﹏╥

展开全部 3 讨论