Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Constraints

• $1 <= k <= nums.length <= 10^5$

• $10^4 <= nums[i] <= 10^4$

Solutions

1. Brute-Force Method

The most straightforward solution is to sort the array in decreasing order, and then return the element at index k - 1. This solution has a time complexity of O(n log n), where n is the number of elements in the array. This is because the time complexity of sorting an array is O(n log n).

public int FindKthLargest(int[] nums, int k) {
    Array.Sort(nums);
    return nums[nums.Length - k];
}

2. QuickSelect Method

The QuickSelect algorithm is an efficient in-place variation of the QuickSort algorithm. It is used to solve the "selection problem", which is to find the kth smallest (or largest) element in an unordered list. The QuickSelect algorithm works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The time complexity of this algorithm is O(n) in the average case, but can be O(n^2) in the worst case. The space complexity is O(1).

public class Solution {
    private static readonly Random rand = new();
    public int FindKthLargest(int[] nums, int k) {
        return Select(nums, 0, nums.Length - 1, nums.Length - k);
    }

    private int Select(int[] nums, int left, int right, int kSmallest) {
        if (left == right) {
            return nums[left];
        }

        int pivotIndex = rand.Next(left, right);
        pivotIndex = Partition(nums, left, right, pivotIndex);

        if (kSmallest == pivotIndex) {
            return nums[kSmallest];
        } else if (kSmallest < pivotIndex) {
            return Select(nums, left, pivotIndex - 1, kSmallest);
        } else {
            return Select(nums, pivotIndex + 1, right, kSmallest);
        }
    }

    private int Partition(int[] nums, int left, int right, int pivotIndex) {
        int pivot = nums[pivotIndex];
        Swap(nums, pivotIndex, right);
        int storeIndex = left;

        for (int i = left; i <= right; i++) {
            if (nums[i] < pivot) {
                Swap(nums, storeIndex, i);
                storeIndex++;
            }
        }

        Swap(nums, storeIndex, right);
        return storeIndex;
    }

    private void Swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

NOTE: Bài viết này có tiếng Việt. Bạn có thể đọc ở đây.