Kth Largest Element — tìm phần tử lớn thứ K. Quickselect đạt O(n) trung bình thế nào, đánh đổi gì so với heap?

Ý tưởng: Quickselect = một nhánh của quicksort. Chọn pivot, partition mảng; pivot rơi đúng vị trí cuối cùng của nó sau sắp xếp. Nếu vị trí đó đúng K thì xong; nếu không, chỉ đệ quy vào một nửa chứa đáp án (bỏ nửa kia) → trung bình O(n).

Đánh đổi vs heap:
- Heap kích thước K: O(n log K), ổn định, không sửa input, hợp streaming.
- Quickselect: O(n) trung bình nhưng O(n²) xấu nhất (pivot lệch), sửa input tại chỗ. Chọn pivot ngẫu nhiên để tránh worst-case.

function findKthLargest(nums: number[], k: number): number {
  const target = nums.length - k // chỉ số khi sắp tăng dần
  const partition = (l: number, r: number): number => {
    const pivot = nums[r]; let i = l
    for (let j = l; j < r; j++)
      if (nums[j] <= pivot) { [nums[i], nums[j]] = [nums[j], nums[i]]; i++ }
    [nums[i], nums[r]] = [nums[r], nums[i]]
    return i
  }
  let lo = 0, hi = nums.length - 1
  while (true) {
    const p = partition(lo, hi)
    if (p === target) return nums[p]
    if (p < target) lo = p + 1
    else hi = p - 1
  }
}

Độ phức tạp: trung bình O(n), xấu nhất O(n²); bộ nhớ O(1) (bản lặp).

Lưu ý: "Lớn thứ K" = chỉ số n - k khi sắp tăng dần — lệch chỗ này là bug kinh điển.