为何同时间复杂度的两种算法在LeetCode第K大元素题一通过一超时？

我在LeetCode解决「数组中的第K个最大元素」问题时，尝试了两种理论平均时间复杂度均为O(n)的方法，但其中一种通过所有测试用例，另一种在大型用例中超时。以下是具体实现和原因分析：

方法1：标准Quickselect（已通过） #

int quickselect(int* nums, int l, int r, int k) {
    if (l == r)
        return nums[k];
    int partition = nums[l], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (nums[i] < partition);
        do j--; while (nums[j] > partition);
        if (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    if (k <= j) return quickselect(nums, l, j, k);
    else return quickselect(nums, j + 1, r, k);
}

int findKthLargest(int* nums, int numsSize, int k) {
    return quickselect(nums, 0, numsSize - 1, numsSize - k);
}

方法2：改进版快速排序（超时） #

void q(int nums[], int left, int right, int k) {
    if (left >= right) return;

    int piv = nums[left];  // Select the first element as the pivot
    int l = left, r = right;

    while (l < r) {
        // From right to left, find the first element less than the pivot
        while (l < r && nums[r] <= piv) r--;
        nums[l] = nums[r];

        // From left to right, find the first element greater than the pivot
        while (l < r && nums[l] >= piv) l++;
        nums[r] = nums[l];
    }

    nums[l] = piv;  // Place the pivot in the correct position

    if (l == k) return;  // Found the kth element
    if (l < k) q(nums, l + 1, right, k);  // Search the right side
    else q(nums, left, l - 1, k);  // Search the left side
}

int findKthLargest(int* nums, int numsSize, int k) {
    q(nums, 0, numsSize - 1, k - 1);  // We use k - 1 because the array is 0-indexed
    return nums[k - 1];  // Return the kth largest element
}

超时原因分析 #

虽然两种算法的平均时间复杂度都是O(n)，但在最坏场景下的表现差异巨大：

1. 分区逻辑对重复元素的处理能力不同

   • 方法1的分区用do-while跳过等于pivot的元素，最终会把等于pivot的元素分散到分区两侧，保证即使数组全是重复元素，分区也能接近中间位置，避免极端情况。
   • 方法2的分区条件是nums[r] <= piv和nums[l] >= piv，当数组存在大量重复元素时，pivot选第一个元素会导致分区后l直接走到right，每次递归只减少一个元素，时间复杂度退化为O(n²)，这是超时的核心原因。

2. 递归终止与搜索范围的效率差异

   • 方法1在l == r时直接返回目标值，减少不必要的递归；而方法2在left >= right时返回，但极端场景下递归深度会远超方法1，进一步拖慢执行速度。

3. pivot选择的鲁棒性
   两种方法都固定选第一个元素作为pivot，这本身就存在最坏情况风险，但方法1的分区逻辑一定程度上抵消了这个问题，而方法2的分区逻辑放大了这个缺陷。如果给方法2加上随机选择pivot的逻辑，能大幅降低最坏情况出现的概率。

内容的提问来源于stack exchange，提问作者459zyt