5.2节 215.快速选择 超时

[yorhaha]

PDF 中给出的解法超时。这是由于 LeetCode 构造了一个绝大多数元素相等的测试样例，导致没有处理好边界问题就会超时。

[1,2,3,4,5,1,1,1, ...... , 1,1,1,-5,-4,-3,-2,-1]

p.s. 如果直接对数组排序，那么使用 STL 的 sort 不会超时，但是使用 PDF 给出的快速排序算法也是会超时的。

改进后的代码如下（只修改了 quickSelection 函数的边界调整细节）：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int l = 0, r = nums.size() - 1, target = nums.size() - k;
        while (l < r) {
            int mid = quickSelection(nums, l, r);
            if (mid == target) {
                return nums[mid];
            }
            if (mid < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return nums[l];
    }

    int quickSelection(vector<int>& nums, int l, int r) {
        int partition = nums[l], i = l, j = r + 1;
        while (true) {
            i += 1;
            while (i < r && nums[i] < partition) {
                i += 1;
            }
            j -= 1;
            while (j > l && nums[j] > partition) {
                j -= 1;
            }
            if (i >= j)
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[l], nums[j]);
        return j;
    }
};

[changgyhub]

感谢指正！我的Overleaf会员过期了，没办法compile这么大的pdf，等我看看啥时候开个会员改一改....