class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
       if(nums.size() < k || k < 1) return -1;

        int left = 0, right = nums.size()-1;
        while(left < right) { //循环条件是左右闭区间至少有1个数，一旦找到第k大的数就跳出循环 Bug2:<会忽略掉只有一个元素的情况,其他情况也会不对,<=才对
            int index = left + (rand() % (right-left+1));
            swap(nums, index, right);

            int cur = left; //left-1也可,下面的写法就要改
            for(int i = left; i < right; i++) {
                if(nums[i] > nums[right]) {
                    swap(nums, cur++, i);
                }
            }
            swap(nums, cur, right); //现在以cur为中心,左边均是比他大的，右边是小于等于的

            if(cur > k-1) { //Bug1：第k大的是排序完第k-1个，0--k-1是最大的k个(内部是乱序)
                right = cur-1;
            }
            else if(cur < k-1) {
                left = cur+1;
            }
            else{
                return nums[cur];
            }
        }
        return -1;
    }

    void swap(vector<int>& nums, int left, int right) {
        if(left == right) return;

        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
};

 

• 点赞
• 收藏
• 分享
• • 文章举报

chengda321 发布了97 篇原创文章 · 获赞 11 · 访问量 2453 私信 关注