Phần tử lớn thứ K: ba cách tránh phải sort toàn bộ mảng

Nhìn vào LeetCode 215 lần đầu, bước đi rõ ràng nhất là sort(reverse=True), trả về nums[k-1]. Đúng. Cũng chính là câu trả lời khiến người phỏng vấn hỏi tiếp "có cách nào tốt hơn không?" — vì bạn vừa dùng O(n log n) để tìm một phần tử, bỏ phí toàn bộ công sức so sánh với n - k phần tử không cần thiết.

Bài toán (LeetCode 215): cho mảng số nguyên nums và số nguyên k, trả về phần tử lớn thứ k theo thứ tự sắp xếp. Phần tử trùng lặp vẫn tính — nếu mảng là [5, 5, 4] và k=2, đáp án là 5, không phải 4. Gợi ý trong đề bài ("Bạn có thể giải mà không cần sort không?") là dấu hiệu có hai cách tiếp cận tốt hơn.

Những gì constraint buộc phải làm

1 <= k <= nums.length <= 10^5. Ba điều rút ra từ đây:

k luôn hợp lệ. Không cần guard cho trường hợp k > n. Bài đảm bảo đáp án tồn tại.

n có thể đến 100,000. Giải pháp O(n^2) quá chậm — tệ nhất là 10 tỷ phép so sánh. Sort thuần O(n log n) chạy được. Nhưng O(n) trung bình còn tốt hơn nữa.

-10^4 <= nums[i] <= 10^4. Phạm vi giá trị bị chặn: 20,001 giá trị phân biệt. Điều này cho phép dùng bucket sort (O(n) worst case bằng cách đếm số lần xuất hiện), dù heap và QuickSelect tổng quát hơn và không cần đến nó.

Không lo overflow với giá trị phần tử. Nhưng trong C#, khi tính (left + right) / 2 ở QuickSelect, phép cộng index có thể overflow nếu cả hai gần Int32.MaxValue. Dùng left + (right - left) / 2.

Brute force: sort rồi lấy index

Sort giảm dần và trả về nums[k-1] là baseline. Trong thi đấu tôi sẽ viết cái này trước để có điểm, rồi tối ưu sau.

from typing import List
 
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k - 1]

public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        Array.Sort(nums, (a, b) => b.CompareTo(a));
        return nums[k - 1];
    }
}

Time O(n log n). Space O(1) cho sort in-place (Timsort của Python thực ra dùng O(n) scratch space nội bộ, nhưng đó là chi tiết implementation). Độ đúng thì không cần bàn. Vấn đề là bạn dùng O(n log n) phép so sánh để xác định thứ tự của mọi phần tử, rồi bỏ đi tất cả trừ index k-1.

Với constraint của bài (n <= 10^5), cách này pass judge LeetCode. Trong môi trường production khi query chạy hàng triệu lần trên mảng lớn, bạn sẽ quan tâm đến độ phức tạp hơn.

Min heap: giữ đúng k phần tử

Insight cốt lõi: nếu muốn phần tử lớn thứ k, tôi chỉ cần theo dõi k phần tử lớn nhất đã thấy cho đến hiện tại. Tại mọi thời điểm, phần tử nhỏ nhất trong số k phần tử đó là ứng viên cho đáp án. Min heap kích thước k làm chính xác điều này.

• Nếu heap có ít hơn k phần tử, push ngay.
• Nếu heap đã có k phần tử và phần tử mới lớn hơn root của heap (phần tử nhỏ nhất trong top-k hiện tại), pop root và push phần tử mới. Phần tử mới vừa hạ gục phần tử yếu nhất trong top-k trước đó.
• Nếu phần tử mới nhỏ hơn hoặc bằng root, nó không thể lọt vào top-k. Bỏ qua.

Sau khi xử lý xong n phần tử, heap giữ đúng k giá trị lớn nhất đã gặp. Root — nhỏ nhất trong số chúng — là phần tử lớn thứ k.

import heapq
from typing import List
 
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap: List[int] = []
 
        for num in nums:
            if len(min_heap) < k:
                heapq.heappush(min_heap, num)
            elif num > min_heap[0]:
                heapq.heapreplace(min_heap, num)
 
        return min_heap[0]

using System.Collections.Generic;
 
public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        // PriorityQueue<TElement, TPriority> có từ .NET 6+.
        // Priority bằng chính giá trị phần tử để tạo min heap.
        var minHeap = new PriorityQueue<int, int>();
 
        foreach (int num in nums) {
            if (minHeap.Count < k) {
                minHeap.Enqueue(num, num);
            } else if (num > minHeap.Peek()) {
                minHeap.Dequeue();
                minHeap.Enqueue(num, num);
            }
        }
 
        return minHeap.Peek();
    }
}

Trace qua nums = [3,2,1,5,6,4], k = 2

Bước 2 là nơi tính chất min heap phát huy tác dụng. Sau khi push 3 và 2, root của heap là 2 (phần tử nhỏ hơn). Khi 1 đến, nó thua 2 và bị loại. Khi 5 đến, nó thắng 2 và thay thế — heap giờ giữ [3, 5], hai giá trị lớn nhất đã thấy. Sau khi 6 đẩy 3 ra, heap là [5, 6]. Phần tử 4 cuối cùng không đánh bại được 5. Root cuối: 5. Đúng.

Time O(n log k). Mỗi phần tử trong số n phần tử kích hoạt nhiều nhất một push và một pop từ heap, cả hai đều O(log k). Space O(k) — chỉ heap, không phải toàn bộ input.

Khi k nhỏ so với n, điều này nhanh hơn sort một cách đáng kể. Với k=10 và n=100,000, heap xử lý mỗi phần tử trong O(log 10) ≈ 3.3 phép so sánh thay vì O(log 100,000) ≈ 17.

QuickSelect: partition về phía đáp án

QuickSelect là phần của QuickSort bạn giữ lại khi chỉ muốn một đáp án. Trong QuickSort, bạn partition và đệ quy cả hai nửa. Trong QuickSelect, bạn partition và đệ quy vào duy nhất nửa chứa phần tử lớn thứ k.

Cách partition hoạt động: chọn một pivot, sắp xếp lại mảng sao cho mọi thứ lớn hơn pivot ở bên trái và nhỏ hơn ở bên phải, rồi đặt pivot vào vị trí cuối cùng của nó. Sau partition, nếu pivot rơi vào index k-1 (0-indexed, coi mảng sắp xếp giảm dần), xong — đó chính là đáp án. Nếu pivot quá xa bên phải (index > k-1), đáp án nằm trong nửa trái. Quá xa bên trái (index < k-1), tìm ở nửa phải.

Random hóa việc chọn pivot tránh worst case O(n^2) xảy ra khi luôn chọn phần tử min hoặc max (điều này xảy ra có quy luật với input đã sort nếu bạn luôn chọn phần tử cuối làm pivot).

import random
from typing import List
 
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quickselect(left: int, right: int) -> int:
            pivot_idx = random.randint(left, right)
            nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
 
            pivot = nums[right]
            store = left
 
            for i in range(left, right):
                if nums[i] > pivot:
                    nums[store], nums[i] = nums[i], nums[store]
                    store += 1
 
            nums[store], nums[right] = nums[right], nums[store]
 
            if store == k - 1:
                return nums[store]
            elif store > k - 1:
                return quickselect(left, store - 1)
            else:
                return quickselect(store + 1, right)
 
        return quickselect(0, len(nums) - 1)

using System;
 
public class Solution {
    private readonly Random _rand = new Random();
 
    public int FindKthLargest(int[] nums, int k) {
        return QuickSelect(nums, 0, nums.Length - 1, k);
    }
 
    private int QuickSelect(int[] nums, int left, int right, int k) {
        int pivotIdx = _rand.Next(left, right + 1);
        Swap(nums, pivotIdx, right);
 
        int pivot = nums[right];
        int store = left;
 
        for (int i = left; i < right; i++) {
            if (nums[i] > pivot) {
                Swap(nums, store, i);
                store++;
            }
        }
 
        Swap(nums, store, right);
 
        if (store == k - 1)      return nums[store];
        if (store > k - 1)       return QuickSelect(nums, left, store - 1, k);
        return QuickSelect(nums, store + 1, right, k);
    }
 
    private static void Swap(int[] nums, int i, int j) {
        (nums[i], nums[j]) = (nums[j], nums[i]);
    }
}

Trace qua nums = [3,2,1,5,6,4], k = 2

Giả sử pivot ngẫu nhiên chọn index 5 (giá trị 4). Partition đưa mọi thứ lớn hơn 4 sang trái:

Sau partition: [5, 6, 4, 3, 2, 1]  (các phần tử > 4 di chuyển sang trái)
pivot 4 rơi vào index 2

Index 2 > k-1 = 1, nên tìm bên trái: quickselect(0, 1). Giờ trên [5, 6]. Pivot chọn một trong hai — giả sử 6 (index 1). Không có gì trong khoảng [0, 0] lớn hơn 6, nên store ở lại 0. Swap đặt 6 vào index 1. store=0. store == k-1 = 1? Không. store > k-1? Không. Đệ quy phải: quickselect(1, 1, 2). Một phần tử: pivot là 5. Sau partition store=1. store == k-1 = 1? Đúng. Trả về nums[1] = 5. Đúng.

Trace cho thấy tính chất then chốt: mỗi lần đệ quy làm việc trên mảng con nhỏ hơn nghiêm ngặt, nên thuật toán luôn kết thúc.

Time O(n) trung bình, O(n^2) worst case. Với pivot ngẫu nhiên, số phép so sánh kỳ vọng là O(n) — mỗi tầng đệ quy xử lý n, rồi n/2, rồi n/4 ... tổng lại thành 2n. Space O(1) cho partition (in-place), nhưng stack đệ quy sâu O(log n) trung bình, O(n) worst case.

Một điều cần biết rõ: worst case không chỉ là lý thuyết. Nếu chạy phiên bản không randomize (luôn chọn nums[right] làm pivot) trên mảng đã sort giảm dần với k=1, mỗi lần partition đặt pivot vào vị trí 0 và đệ quy trên n-1 phần tử. Đó chính xác là O(n^2). Pivot ngẫu nhiên giải quyết pathology này.

Các edge case quan trọng

k = 1 (tìm phần tử lớn nhất). Cả ba cách trả về đúng. Với heap, heap giữ một phần tử — maximum đang chạy. Với QuickSelect, đáp án là phần tử tận cùng bên trái sau khi partition xong.

k = n (tìm phần tử nhỏ nhất). QuickSelect đệ quy cho đến mảng con tận cùng bên phải. Heap xử lý tất cả n phần tử, giữ n phần tử (toàn bộ mảng), và root là minimum. Đúng.

Tất cả phần tử giống nhau, ví dụ [7,7,7,7], k=3. Brute force: nums[2] = 7. Heap: mọi phần tử bằng root, nên num > min_heap[0] luôn false sau khi heap đầy — heap giữ [7,7,7] và trả về 7. QuickSelect: vòng lặp partition không bao giờ swap vì không có phần tử nào strictly lớn hơn pivot — store ở lại left, pivot đặt vào left. Đệ quy phải liên tục. Cuối cùng mảng con đến index thứ k. Trả về 7. Tất cả đúng.

Đã sort giảm dần, k=1, QuickSelect không randomize. Như đã phân tích: O(n^2) phép so sánh. Đây là lý do tồn tại phiên bản randomize. Luôn random hóa pivot.

Một phần tử, k=1. Cả ba cách trả về phần tử đó. Với heap, nhánh len(min_heap) < k push phần tử duy nhất, vòng lặp kết thúc, return min_heap[0].

So sánh độ phức tạp

Trong thực tế tôi sẽ dùng gì

Với phỏng vấn khi bài hỏi "tìm phần tử lớn thứ k trong mảng tĩnh", tôi sẽ dùng min heap. Code gọn, complexity dễ giải thích, space dùng có kiểm soát. QuickSelect có average time tốt hơn, nhưng nó mutate input (đôi khi là vấn đề), việc random hóa dễ quên, và câu chuyện worst case đòi hỏi giải thích tại sao O(n^2) vẫn chấp nhận được.

Approach min heap cũng tổng quát hóa được cho streaming input — nếu nums đến dạng data stream thay vì mảng đầy đủ, thuật toán heap chạy không thay đổi gì. QuickSelect về căn bản không làm được điều này; bạn cần toàn bộ mảng để partition. Đúng cái tổng quát hóa đó là thứ LeetCode 703 (Kth Largest Element in a Stream) kiểm tra.

Nếu biết k nhỏ — giả sử luôn nhỏ hơn 100 — min heap thắng cả về constant factor. Log cơ 2 của 100 chưa đến 7. Mỗi heap operation dưới 7 phép so sánh. Sort tốn trung bình 17 phép so sánh mỗi phần tử với n=100,000.

Nếu ai đó yêu cầu mutation in-place và O(n) average time, tôi dùng QuickSelect với pivot ngẫu nhiên và nói rõ về worst case. Trong thực tế tình huống đó ít gặp hơn các bài phỏng vấn gợi ý.

Pattern cốt lõi: duy trì top-K

Mental model từ bài này là top-K heap pattern: dùng min heap kích thước k để duy trì k phần tử lớn nhất (hoặc max heap kích thước k cho k phần tử nhỏ nhất). Root heap luôn là ứng viên cho đáp án. Phần tử mới chỉ vào được nếu có thể hạ gục phần tử yếu nhất của top-k hiện tại.

Pattern này xuất hiện trong một cụm bài liên quan:

LeetCode 703 — Kth Largest Element in a Stream. Cùng heap đó, nhưng các phần tử đến từng cái một. Bạn không bao giờ có đủ mảng, nên QuickSelect không dùng được. Heap là giải pháp sạch duy nhất.

LeetCode 347 — Top K Frequent Elements. Bạn không select theo giá trị thô mà theo tần suất. Build frequency map trước, rồi áp dụng cùng min heap kích thước k trên các tuple (tần_suất, phần_tử). Logic heap giống hệt; khóa so sánh thay đổi.

LeetCode 973 — K Closest Points to Origin. Khoảng cách đến gốc tọa độ thay cho giá trị thô. Min heap kích thước k trên (khoảng_cách, điểm). Lại cùng cấu trúc.

LeetCode 692 — Top K Frequent Words. Thêm tiebreaking theo thứ tự từ điển khi tần suất bằng nhau. Phép so sánh heap trở thành (tần_suất, từ) với từ so sánh đảo ngược. Pattern vẫn đúng; khóa so sánh phức tạp hơn.

Trong mỗi bài đó, một khi nhận ra "mình đang duy trì k phần tử tốt nhất theo tiêu chí nào đó", heap đặt vào ngay lập tức. Tiêu chí thay đổi, cấu trúc không thay đổi.

Đây là bài đầu tiên trong series heap-priority-queue vì nó là phát biểu gọn nhất của top-K pattern. Mọi thứ tiếp theo xây dựng trên nó: khóa so sánh phức tạp hơn, heap dùng cho scheduling hoặc merging, và các bài toán pop từ heap giữa vòng lặp thay vì chỉ ở cuối.