Leetcode 剑指 Offer 40. 最小的k个数(DAY 235)---- 后端面试题

文章目录


原题题目


Leetcode 剑指 Offer 40. 最小的k个数(DAY 235)---- 后端面试题


代码实现(首刷自解 快排)


class Solution {
public:
    int partition(vector<int>& arr,int left,int right)
    {
        swap(arr[(left + right) / 2],arr[left]);
        int low = arr[left],l = left,r = right + 1,size = arr.size();
        while(l < r)
        {
            while(l < right && arr[++l] <= low);
            while(r > left  && arr[--r] >= low);

            if(l >= r)   break;
            swap(arr[l],arr[r]);
        }

        swap(arr[left],arr[r]);
        return r;
    }

    void quick_sort(vector<int>& arr,int left,int right,int k)
    {
        if(left >= right)   return;

        int mid = partition(arr,left,right);

        if(mid == k)    return;
        quick_sort(arr,left,mid-1,k);
        quick_sort(arr,mid+1,right,k);
    }

    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        quick_sort(arr,0,arr.size()-1,k);
        return vector<int>(arr.begin(),arr.begin() + k);
    }
};
上一篇:PHP 冒泡排序


下一篇:Golang实现经典排序算法【一】—冒泡、选择、插入、希尔