首页 > 【牛客题霸每日一题】NC88 寻找第K大 题解
头像
BNDSBilly
编辑于 2020-12-07 11:07
+ 关注

【牛客题霸每日一题】NC88 寻找第K大 题解

快速排序每次在 l, r 范围内递归地进行元素排序,加入参数 k ,使得快速排序每次只在递归的一侧进行,代码如下:
class Finder {
public:
    int partition(vector<int>& arr, int left, int right) {
        int pivot = left;
        int lt = left + 1;
        int gt = right;
        while (true) {
            while (lt <= right && arr[lt] < arr[pivot]) lt++;
            while (gt >= left && arr[gt] > arr[pivot]) gt--;
            if (lt > gt) break;
            swap(arr[lt], arr[gt]);
            lt++;
            gt--;
        }
        swap(arr[pivot], arr[gt]);
        return gt;
    }
    
    int findKth(vector<int> arr, int n, int k) {
        // write code here
        k = n - k;
        int left = 0, right = arr.size() -1;
        int pivot = 0;
        do {
            pivot = partition(arr, left, right);
            if(pivot == k){
                break;
            }else if(pivot > k){
                right = pivot - 1;
            }else {
                left = pivot + 1;
            }
        }while(true);        

        return arr[pivot];
    }
};


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐