Một dạng bài toán phổ biến trong lập trình đó là dạng yêu cầu tìm k phần tử tốt nhất, "tốt nhất" ở đây là phụ thuộc vào bài toán. Cách dễ dàng nhất để giải quyết những bài toán này là sắp xếp đầu vào theo các yêu cầu được đưa ra bởi bài toán, sau đó trả về top k phần tử. Cách này có độ phức tạp thuật toán là $O(n \cdot \log n)$ với n là độ dài của đầu vào.

Thay vào đó, nếu sử dụng heap, chúng ta có thể tìm thấy top k phần tử trong thời gian $O(n \cdot \log k)$. Theo logic, k < n, vì vậy đây là một sự cải thiện. Trên thực tế, vì $\log$ dù sao cũng khá nhanh nên tốc độ tăng sẽ không phải là vấn đề lớn. Nhưng khi câu hỏi phỏng vấn đưa ra những dạng bài đó thì chính những cải thiện nhỏ này là điều mà nhà tuyển dụng tìm kiếm.

Sự cải thiện ở đây là gì? Tạo một heap tối đa khi bắt đầu, lặp lại đầu vào trong khi đẩy mọi phần tử lên heap (theo yêu cầu của bài toán) và lấy ra khỏi heap khi kích thước vượt quá k. Bởi vì kích thước của heap bị giới hạn bởi k nên các thao tác với heap trong trường hợp xấu nhất là $O(\log k)$. Nhân số này với n lần lặp để có thời gian $O(n \cdot \log k)$. Bởi vì chúng ta đang sử dụng heap tối đa và lấy ra khỏi heap theo yêu cầu của bài toán nên thao tác lấy ra sẽ loại bỏ các phần tử "xấu nhất", do đó, cuối cùng, k phần tử "tốt nhất" sẽ vẫn còn trong heap.

[___NOTE_Hãy xem xét một số ví dụ._NOTE___]

[___QUESTION_

Ví dụ 1: Tìm K phần tử xuất hiện nhiều nhất

Cho mảng số nguyên nums và số nguyên k, trả về k phần tử xuất hiện nhiều nhất.

_QUESTION___]

Chúng ta có thể sử dụng bảng băm để tìm và lưu tần suất của từng phần tử. Sau đó, chúng ta sắp xếp các khóa bảng băm bằng bộ so sánh tùy chỉnh (theo giá trị). Điều này sẽ cho độ phức tạp thuật toán là $O(n \cdot \log n)$ trong đó n = nums.length.

Khi bạn lấy phần tử ra từ heap tối thiểu, heap sẽ loại bỏ phần tử nhỏ nhất trong thời gian logarit. Chúng ta có thể tìm tần suất bằng cách sử dụng bảng băm như trước đây, sau đó cho các khóa có tần suất tương ứng vào heap. Khi kích thước heap vượt quá k, chúng ta có thể lấy ra khỏi heap trong thời gian $O(\log k)$. Vì chúng ta giới hạn kích thước của heap là k,nên cuối cùng heap sẽ chứa k phần tử xuất hiện nhiều nhất, với độ phức tạp thuật toán là $O(n \cdot \log k)$.

VIDEO

C
C++
Java
Python 3
HTML
Python ML
javascript
C#

class Solution {
public:
    vector topKFrequent(vector& nums, int k) {
        unordered_map<int, int> counts;
        for (int num: nums) {
            counts[num]++;
        }
        
        priority_queue<pair<int, int>> heap;
        for (auto [key, val]: counts) {
            heap.push({-val, key});
            if (heap.size() > k) {
                heap.pop();
            }
        }
        
        vector ans;
        while (heap.size() > 0) {
            ans.push_back(heap.top().second); heap.pop();
        }

        return ans;
    }
};

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num: nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        
        PriorityQueue heap = new PriorityQueue<>((n1, n2) -> counts.get(n1) - counts.get(n2));
        for (int num: counts.keySet()) {
            heap.add(num);
            if (heap.size() > k) {
                heap.remove();
            }
        }
        
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = heap.remove();
        }
        
        return ans;
    }
}

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counts = Counter(nums)
        heap = []
        
        for key, val in counts.items():
            heapq.heappush(heap, (val, key))
            if len(heap) > k:
                heapq.heappop(heap)
        
        return [pair[1] for pair in heap]

[___QUESTION_

Ví dụ 2: Tìm K Phần Tử Gần Nhất

Cho mảng số nguyên được sắp xếp arr, hai số nguyên k và x, trả về k số nguyên gần x nhất. Kết quả cũng nên được sắp xếp theo thứ tự tăng dần. Nếu có ràng buộc, hãy lấy các phần tử nhỏ hơn.

_QUESTION___]

Trong bài toán trước, chúng ta cần tìm tần suất lớn nhất, vì vậy chúng ta cho các tần suất vào heap. Trong bài toán này, chúng ta cần tìm chênh lệch tối thiểu, vì vậy cho chênh lệch vào heap. Khi muốn số lớn nhất, nếu sử dụng heap tối thiểu thì thao tác lấy ra sẽ loại bỏ các phần tử nhỏ hơn. Trong bài toán này, chúng ta muốn tìm chênh lệch tối thiểu, vì vậy nếu sử dụng heap tối đa thì thao tác lấy ra sẽ loại bỏ chênh lệch tối đa.

Bài toán cho biết các ràng buộc nên bị phá vỡ bởi kích thước các phần tử. Khi bạn cho các phần tử có thứ tự (như tupple hoặc danh sách) vào heap, heap sẽ đi qua từng phần tử để xác định thứ tự. Nếu chỉ số đầu tiên bị ràng buộc thì heap sẽ chuyển sang chỉ số thứ hai, v.v. Ví dụ: nếu chúng ta có một heap tối đa với (5, 3) và (5, 13), vì chỉ số đầu tiên được ràng buộc với 5, heap sau đó sẽ so sánh 3 với 13. 13 lớn hơn, vì vậy (5, 13) được coi là lớn hơn về tổng thể và sẽ được lấy ra tiếp theo.

VIDEO

C
C++
Java
Python 3
HTML
Python ML
javascript
C#

class Solution {
public:
    vector findClosestElements(vector& arr, int k, int x) {
        priority_queue<pair<int, int>> heap;
        
        for (int num: arr) {
            int distance = abs(x - num);
            heap.push(pair(distance, num));
            if (heap.size() > k) {
                heap.pop();
            }
        }
        
        vector ans;
        while (heap.size() > 0) {
            ans.push_back(heap.top().second); heap.pop();
        }
        
        sort(ans.begin(), ans.end());
        return ans;
    }
};

class Solution {
    public List findClosestElements(int[] arr, int k, int x) {
        PriorityQueue heap = new PriorityQueue<>((n1, n2) -> {
            if (Math.abs(n1 - x) == Math.abs(n2 - x)) {
                return n2 - n1;
            }
            
            return Math.abs(n2 - x) - Math.abs(n1 - x);
        });

        for (int num: arr) {
            heap.add(num);
            if (heap.size() > k) {
                heap.remove();
            }
        }
        
        List ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ans.add(heap.remove());
        }
        
        Collections.sort(ans);
        return ans;
    }
}

import heapq

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        heap = []
        
        for num in arr:
            distance = abs(x - num)
            heapq.heappush(heap, (-distance, -num))
            if len(heap) > k:
                heapq.heappop(heap)
        
        return sorted([-pair[1] for pair in heap])

Độ phức tạp thuật toán là $O((n+k) \cdot \log k)$, trong đó n là độ dài của mảng đầu vào. Kích thước của heap không bao giờ vượt quá k, vì vậy các thao tác đẩy và lấy ra là $O(\log k)$, mà chúng ta thực hiện n lần. Sau đó, chúng ta cần thời gian $O(k \cdot \log k)$ ở cuối để sắp xếp đầu ra. Thuật toán này thực sự rất chậm so với các cách tiếp cận khác vì nó không khai thác được yếu tố là mảng đầu vào đã được sắp xếp - nhưng ở đây sử dụng thuật toán để làm ví dụ cho cách sử dụng heap trong các bài toán "top k". Cách tiếp cận này vẫn nhanh hơn sắp xếp bằng bộ so sánh tùy chỉnh, một cách làm khá thông thường.

Dạng này tương đối đơn giản nhưng vẫn cần thiết phải biết vì người phỏng vấn sẽ tìm kiếm bất kỳ khả năng tối ưu hóa nào. Bạn hãy thử làm các bài tập theo phương pháp này trước khi tiếp tục bài tiếp theo.

Top K