如何修改Randomized-select算法的kthSmallest方法以查找第k大元素？

Hey there! Since you're diving into the Randomized-Select algorithm and want to adapt the kthSmallest method to find the kth largest element, let's walk through two straightforward approaches to do this.

Approach 1: Reuse the Existing kthSmallest Function #

The simplest way to get the kth largest element is to leverage the relationship between kth largest and kth smallest:

For an array segment from index l to r (total elements = n = r - l + 1), the kth largest element is exactly the (n - k + 1)th smallest element.

For example:

• In an array of 5 elements, the 1st largest is the 5th smallest.
• The 2nd largest is the 4th smallest.

Here's how you can implement this without modifying your original kthSmallest code:

// Assume your existing kthSmallest function looks like this
int partition(int arr[], int l, int r) {
    int pivot = arr[r];
    int i = l;
    for (int j = l; j < r; j++) {
        if (arr[j] <= pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[r]);
    return i;
}

int kthSmallest(int arr[], int l, int r, int k) {
    if (k > 0 && k <= r - l + 1) {
        int pos = partition(arr, l, r);
        if (pos - l == k - 1)
            return arr[pos];
        if (pos - l > k - 1)
            return kthSmallest(arr, l, pos - 1, k);
        return kthSmallest(arr, pos + 1, r, k - pos + l - 1);
    }
    return INT_MAX; // Return error value if k is invalid
}

// New kthLargest function that reuses kthSmallest
int kthLargest(int arr[], int l, int r, int k) {
    int totalElements = r - l + 1;
    // Calculate the equivalent k for kth smallest
    int equivalentK = totalElements - k + 1;
    return kthSmallest(arr, l, r, equivalentK);
}

This approach is great because it reuses your existing, tested code—no need to rewrite core logic.

Approach 2: Modify the Partition Logic for Direct kth Largest Search #

If you prefer a more direct implementation (without translating k values), you can adjust the partition step to sort elements in descending order instead of ascending. Here's how:

1. Modify the partition function: Instead of moving elements smaller than the pivot to the left, move elements larger than or equal to the pivot to the left.
2. Adjust the kthLargest logic: The recursive checks will now compare k against the number of elements larger than the pivot (instead of smaller).

// Partition function modified for descending order
int partitionDescending(int arr[], int l, int r) {
    int pivot = arr[r];
    int i = l;
    for (int j = l; j < r; j++) {
        // Swap elements >= pivot to the left
        if (arr[j] >= pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[r]);
    return i;
}

// Direct kthLargest implementation
int kthLargest(int arr[], int l, int r, int k) {
    if (k > 0 && k <= r - l + 1) {
        int pos = partitionDescending(arr, l, r);
        // pos - l = number of elements larger than arr[pos]
        if (pos - l == k - 1)
            return arr[pos];
        // k is in the left segment (larger elements)
        if (pos - l > k - 1)
            return kthLargest(arr, l, pos - 1, k);
        // k is in the right segment (smaller elements), adjust k
        return kthLargest(arr, pos + 1, r, k - (pos - l + 1));
    }
    return INT_MAX; // Error value for invalid k
}

This approach makes the logic explicitly about finding the kth largest element, which might be easier to follow if you're debugging or explaining the code later.

Both approaches run in expected linear time, just like the original Randomized-Select algorithm—perfect for unsorted arrays!

内容的提问来源于stack exchange，提问作者Pedro Martins