题解 | #寻找第K大#

寻找第K大

https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf

class Solution {
public:

    void swap(int &a, int &b) {
        int temp = a;
        a = b;
        b = temp;
    }
    
    int _qS(vector<int> &arr, int l, int r) {
        swap(arr[l], arr[(l+r)/2]);    // 选区间中间的点,避免极端情况导致时间复杂度达到n2
        int temp = arr[l];
        while(l < r) {
            while(l < r && arr[r] >= temp) --r;
            arr[l] = arr[r];
            while(l < r && arr[l] <= temp) ++l;
            arr[r] = arr[l];
        }
        arr[l] = temp;
        return l;
    }
    
    void qS(vector<int> &arr, int l, int r, int target) {
        if(l < r) {
            int mid = _qS(arr, l, r);
            if(mid == target) return;
            else if(mid > target) qS(arr, l, mid, target);    //只往一个方向递归
            else qS(arr, mid+1, r, target);
        }
    }
    
    int findKth(vector<int> a, int n, int K) {
        // write code here
        if(n == 0) return -1;
        qS(a, 0, n-1, n-K);
        return a[n-K];
    }
};

题目意思很好理解,快排也好理解,有两个关键的问题。
第一个是找到mid之后通过比较和K的大小关系,只往一个方向递归快排;
第二个是快排的过程中为了避免极端情况,选取中间点的时候不要选最左边那个点,选个中间点之类的,要不会超时。
全部评论

相关推荐

头像
05-09 00:54
已编辑
前端工程师
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务