- Định nghĩa trung vị: Với \(n\) phần tử đã sắp xếp tăng dần, nếu \(n\) lẻ thì trung vị là phần tử đứng chính giữa (chỉ số \(\lfloor n/2 \rfloor\)); nếu \(n\) chẵn thì trung vị là trung bình cộng của hai phần tử đứng giữa (chỉ số \(n/2 - 1\) và \(n/2\)).
- Ý tưởng chia đôi bằng Hai Heap: Chia tập hợp hiện có thành hai nửa cân bằng: Nửa nhỏ (
lower) đặt trong một Max-Heap để luôn nhìn thấy phần tử lớn nhất của nửa nhỏ ở đỉnh; Nửa lớn (upper) đặt trong một Min-Heap để luôn nhìn thấy phần tử nhỏ nhất của nửa lớn ở đỉnh. - Hai bất biến bắt buộc: (1) Bất biến thứ tự: mọi phần tử trong
lower\(\le\) mọi phần tử trongupper(tương đương \(\text{lower.top()} \le \text{upper.top()}\)); (2) Bất biến kích thước: \(|\text{lower}| == |\text{upper}|\) (khi tổng chẵn) hoặc \(|\text{lower}| == |\text{upper}| + 1\) (khi tổng lẻ). - Độ phức tạp tối ưu: Mỗi lệnh thêm số mới
addNum(x)thực hiện từ \(3\) đến \(5\) thao tác đẩy/rút trên heap mất \(O(\log n)\), còn lệnh lấy trung vịfindMedian()chỉ đọc \(1\) hoặc \(2\) đỉnh heap trong thời gian hằng số \(O(1)\).
Tại sao cần tới hai Heap đối đỉnh để giữ trung vị?
Hãy xem xét điều gì xảy ra khi tập dữ liệu tăng dần kích thước sau từng lệnh addNum(x). Để trả lời câu hỏi findMedian(), ta không cần biết thứ tự cụ thể của các phần tử nằm ở hai rìa ngoài cùng — thứ duy nhất ta cần biết là \(1\) (khi \(n\) lẻ) hoặc \(2\) (khi \(n\) chẵn) phần tử nằm ngay tại ranh giới chia đôi tập dữ liệu thành hai phần bằng nhau.
Một hàng đợi ưu tiên (Heap) đơn lẻ chỉ cho phép nhìn thấy phần tử cực đại (Max-Heap) hoặc cực tiểu (Min-Heap) của toàn tập hợp ở đỉnh. Nhưng nếu ta cắt đôi tập dữ liệu đã sắp xếp tại vạch ngăn trung vị:
\[\underbrace{[\;x_1 \le x_2 \le \dots \le x_k\;]}_{\text{Nửa nhỏ (Max-Heap }\texttt{lower}\text{)}} \;\Big|\; \underbrace{[\;y_1 \le y_2 \le \dots \le y_m\;]}_{\text{Nửa lớn (Min-Heap }\texttt{upper}\text{)}}\]
Khi đó, hai phần tử nằm sát vạch ngăn nhất chính là:
- \(x_k\) (phần tử lớn nhất của nửa nhỏ): nằm ngay trên đỉnh của Max-Heap
lower(lower.top()). - \(y_1\) (phần tử nhỏ nhất của nửa lớn): nằm ngay trên đỉnh của Min-Heap
upper(upper.top()).
Nhờ cấu trúc hai đỉnh quay mặt vào nhau này, việc tìm trung vị rút gọn thành phép đọc đỉnh \(O(1)\):
- Nếu tổng số phần tử \(n = k + m\) là số lẻ (quy ước ưu tiên nửa nhỏ nhiều hơn nửa lớn \(1\) phần tử, tức \(k = m + 1\)): trung vị chính là
lower.top(). - Nếu tổng số phần tử \(n = k + m\) là số chẵn (\(k = m\)): trung vị là trung bình cộng
(lower.top() + upper.top()) / 2.0.
[5, 2, 8, 1, 9, 3]. Max-Heap lower giữ nửa nhỏ [1, 2, 3] với đỉnh bằng 3; Min-Heap upper giữ nửa lớn [5, 8, 9] với đỉnh bằng 5. Trung vị được tính ngay trong \(O(1)\) bằng (3 + 5) / 2 = 4.0.Quy trình 2 bước thêm phần tử không cần rẽ nhánh phức tạp
Nhiều ứng viên khi cài đặt hàm addNum(x) cố gắng viết hàng loạt nhánh if-else: kiểm tra xem lower có rỗng không, so sánh x với lower.top() và upper.top(), rồi lại kiểm tra chênh lệch kích thước để chuyển qua chuyển lại. Cách viết đó rất dài và dễ sót ca biên ở những phần tử đầu tiên.
Thay vào đó, ta có quy trình Lọc qua hai tầng (Two-stage Filtering) chỉ gồm \(4\) dòng code cố định, đảm bảo giữ vững đồng thời cả hai bất biến ở mọi bước:
- Bước 1 (Đảm bảo bất biến thứ tự): Đẩy phần tử mới
xvàolower, sau đó rút ngay phần tử lớn nhất ở đỉnhlowerchuyển sangupper:lower.push(x)upper.push(lower.top()); lower.pop()Tại sao phải đi vòng qualower? Vìxcó thể lớn hơn một số phần tử trongupper. Khi đẩyxvàolowerrồi rútmaxcủalowerđẩy sangupper, phần tử được chuyển sangupperchắc chắn lớn hơn hoặc bằng toàn bộ phần còn lại tronglower, giữ nguyên bất biến \(\text{lower.top()} \le \text{upper.top()}\).
- Bước 2 (Đảm bảo bất biến kích thước): Sau Bước 1, kích thước của
lowergiữ nguyên còn kích thước củauppertăng thêm \(1\). Nếu điều này làmuppercó nhiều phần tử hơnlower(upper.size() > lower.size()), ta rút phần tử nhỏ nhất ở đỉnhuppertrả ngược vềlower:if (upper.size() > lower.size()) { lower.push(upper.top()); upper.pop(); }
Chỉ với quy trình ngắn gọn này, sau mọi lệnh addNum(x), ta luôn có \(0 \le |\text{lower}| - |\text{upper}| \le 1\) và mọi phần tử trong lower đều \(\le\) mọi phần tử trong upper.
| Phương pháp lưu trữ luồng dữ liệu | Chi phí thêm số mới addNum(x) |
Chi phí lấy trung vị findMedian() |
Bộ nhớ | Đánh giá trong phỏng vấn |
|---|---|---|---|---|
| Sắp xếp lại mảng mỗi lần | \(O(1)\) (push_back) |
\(O(n \log n)\) (sort) |
\(O(n)\) | Quá chậm khi gọi findMedian nhiều lần. |
| Mảng luôn sắp xếp (Chèn nhị phân) | \(O(n)\) (lower_bound + dịch mảng) |
\(O(1)\) (truy cập chỉ số giữa) | \(O(n)\) | Bị \(O(n^2)\) tổng thời gian cho \(n\) phần tử. |
| Cây nhị phân tìm kiếm cân bằng | \(O(\log n)\) | \(O(\log n)\) hoặc \(O(1)\) (giữ con trỏ giữa) | \(O(n)\) | Khó cài đặt trong Python/Java (C++ có multiset). |
Hai Heap đối đỉnh (lower, upper) |
\(O(\log n)\) (tối đa \(5\) lệnh heap) | \(O(1)\) (đọc đỉnh heap) | \(O(n)\) | Chuẩn mực nhất: ngắn gọn, hằng số cực nhỏ. |
Ví dụ chạy tay từng bước trên luồng [5, 2, 8, 1, 9, 3]
Ta lần theo từng bước biến đổi của Max-Heap lower và Min-Heap upper khi nhận lần lượt 6 số 5, 2, 8, 1, 9, 3:
| Bước | Số mới x |
Sau Bước 1 (Đẩy x vào lower \(\to\) Chuyển đỉnh lower sang upper) |
Cần cân bằng Bước 2 (|upper| > |lower|)? |
Trạng thái cuối: lower (đỉnh in đậm) và upper (đỉnh in đậm) |
Trung vị hiện tại |
|---|---|---|---|---|---|
| 1 | 5 |
lower: [], upper: [5] |
Có (\(1 \gt 0\)) \(\to\) trả 5 về lower |
lower: [5], upper: [] |
5.0 (\(n = 1\) lẻ) |
| 2 | 2 |
lower: [2], upper: [5] |
Không (\(1 == 1\)) | lower: [2], upper: [5] |
\((2 + 5)/2 =\) 3.5 |
| 3 | 8 |
lower: [2], upper: [5, 8] |
Có (\(2 \gt 1\)) \(\to\) trả 5 về lower |
lower: [2, 5], upper: [8] |
5.0 (\(n = 3\) lẻ) |
| 4 | 1 |
lower: [1, 2], upper: [5, 8] |
Không (\(2 == 2\)) | lower: [1, 2], upper: [5, 8] |
\((2 + 5)/2 =\) 3.5 |
| 5 | 9 |
lower: [1, 2], upper: [5, 8, 9] |
Có (\(3 \gt 2\)) \(\to\) trả 5 về lower |
lower: [1, 2, 5], upper: [8, 9] |
5.0 (\(n = 5\) lẻ) |
| 6 | 3 |
lower: [1, 2, 3], upper: [5, 8, 9] |
Không (\(3 == 3\)) | lower: [1, 2, 3], upper: [5, 8, 9] |
\((3 + 5)/2 =\) 4.0 |
Hãy chú ý Bước 6 khi số 3 đi vào: lúc đầu lower đang giữ [1, 2, 5]. Khi đẩy 3 vào lower rồi rút đỉnh lớn nhất của lower là 5 chuyển sang upper, số 3 tự động thế chỗ 5 trong lower, còn 5 trở thành đỉnh nhỏ nhất mới của upper ([5, 8, 9]). Nhờ vậy trung vị mới chuyển mượt mà về (3 + 5) / 2 = 4.0.
Cài đặt bằng C++17, Python và Java 21
Trong C++, std::priority_queue<int> mặc định là Max-Heap, còn Min-Heap được khai báo với bộ so sánh greater<int>. Trong Python, đến bản 3.13 mô-đun heapq chỉ có Min-Heap (từ Python 3.14 có thêm heappush_max, heappop_max), nên code dưới đây dùng cách chạy được trên mọi phiên bản: để biến lower thành Max-Heap, ta đổi dấu phần tử thành -x khi đẩy vào lower và đổi dấu ngược lại -lower[0] khi đọc đỉnh. Trong Java, PriorityQueue<>() mặc định là Min-Heap và new PriorityQueue<>(Collections.reverseOrder()) là Max-Heap.
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class MedianFinder {
priority_queue<long long> lo; // Max-Heap cho nửa nhỏ
priority_queue<long long, vector<long long>, greater<long long>> hi; // Min-Heap cho nửa lớn
public:
void addNum(long long num) {
lo.push(num);
hi.push(lo.top());
lo.pop();
if (hi.size() > lo.size()) {
lo.push(hi.top());
hi.pop();
}
}
double findMedian() const {
if (lo.size() > hi.size()) return (double)lo.top();
return (lo.top() + hi.top()) / 2.0;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) {
vector<long long> s = {5, 2, 10, 4};
MedianFinder mf;
cout << fixed << setprecision(1);
for (size_t i = 0; i < s.size(); i++) {
mf.addNum(s[i]);
if (i) cout << " ";
cout << mf.findMedian();
}
cout << "\n";
return 0;
}
MedianFinder mf;
cout << fixed << setprecision(1);
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
mf.addNum(x);
if (i) cout << " ";
cout << mf.findMedian();
}
cout << "\n";
return 0;
}
import heapq
import sys
class MedianFinder:
def __init__(self):
self.lo = [] # Max-Heap lưu số đối (-x)
self.hi = [] # Min-Heap lưu nguyên bản (x)
def add_num(self, num: int) -> None:
heapq.heappush(self.lo, -num)
heapq.heappush(self.hi, -heapq.heappop(self.lo))
if len(self.hi) > len(self.lo):
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def find_median(self) -> float:
if len(self.lo) > len(self.hi):
return float(-self.lo[0])
return (-self.lo[0] + self.hi[0]) / 2.0
def main():
tokens = sys.stdin.read().split()
if not tokens:
nums = [5, 2, 10, 4]
else:
n = int(tokens[0])
nums = [int(x) for x in tokens[1:1 + n]]
mf = MedianFinder()
outs = []
for x in nums:
mf.add_num(x)
outs.append(f"{mf.find_median():.1f}")
print(" ".join(outs))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static class MedianFinder {
private final PriorityQueue<Long> lo = new PriorityQueue<>(Collections.reverseOrder());
private final PriorityQueue<Long> hi = new PriorityQueue<>();
public void addNum(long num) {
lo.offer(num);
hi.offer(lo.poll());
if (hi.size() > lo.size()) {
lo.offer(hi.poll());
}
}
public double findMedian() {
if (lo.size() > hi.size()) return (double) lo.peek();
return (lo.peek() + hi.peek()) / 2.0;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long[] nums;
if (!sc.hasNextInt()) {
nums = new long[]{5, 2, 10, 4};
} else {
int n = sc.nextInt();
nums = new long[n];
for (int i = 0; i < n; i++) nums[i] = sc.nextLong();
}
MedianFinder mf = new MedianFinder();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < nums.length; i++) {
mf.addNum(nums[i]);
if (i > 0) sb.append(" ");
sb.append(String.format(Locale.US, "%.1f", mf.findMedian()));
}
System.out.println(sb);
}
}
Các lỗi thường gặp và câu hỏi nâng cao trong phỏng vấn
Ba lỗi kỹ thuật cần tránh khi viết code
- Quên đổi dấu khi chuyển phần tử giữa hai Heap trong Python: Trong Python, vì
lowerlưu số đối-xcònupperlưu số thựcx, khi rút đỉnh từlowerđẩy sangupper, bạn bắt buộc phải đổi dấuheapq.heappush(upper, -heapq.heappop(lower)). Nếu quên dấu trừ-, các số âm sẽ tràn sanguppervà làm hỏng hoàn toàn thứ tự. - Tràn số nguyên 32-bit khi tính
(lower.top() + upper.top()) / 2.0: Nếu các phần tử trong luồng dữ liệu có thể đạt tớiINT_MAX(\(2^{31} - 1\)), phép cộng hai số nguyên 32-bitlower.top() + upper.top()trước khi chia cho2.0sẽ bị tràn số. Hãy ép kiểu sangdouble(hoặclong long) ngay từ số hạng đầu tiên:((double)lower.top() + upper.top()) / 2.0. - Cách tự kiểm chứng tại nhà: Khi tự kiểm tra lớp
MedianFinder, hãy tạo một mảng phụarr, mỗi lần gọiaddNum(x)thì thêmxvàoarr, sắp xếp lạiarrvà tính trung vị trực tiếp từarr[n // 2](khi \(n\) lẻ) hoặc(arr[n // 2 - 1] + arr[n // 2]) / 2(khi \(n\) chẵn) để so sánh vớifindMedian(). Hãy thử trên luồng toàn số âm[-5, -10, -3, -1], luồng có nhiều số trùng nhau[2, 2, 2, 2]và luồng giảm dần nghiêm ngặt.
Hai câu hỏi mở rộng (Follow-up) có sẵn trong đề LeetCode 295
Sau khi bạn hoàn thành lời giải hai Heap, người phỏng vấn thường hỏi tiếp hai câu hỏi thiết kế:
- Câu hỏi mở rộng 1: "Nếu toàn bộ các số từ luồng dữ liệu đều là số nguyên nằm trong đoạn \([0, 100]\), bạn có thể tối ưu tốt hơn không?"
- Trả lời: Thay vì dùng hai Heap tốn bộ nhớ \(O(n)\) và thời gian \(O(\log n)\), ta chỉ cần khai báo một mảng đếm tần suất cố định
cnt[101](tốn \(O(1)\) bộ nhớ) và biến tổng số phần tửtotal. Mỗi lệnhaddNum(x)chỉ thực hiệncnt[x]++; total++;trong \(O(1)\). Khi gọifindMedian(), ta duyệtvtừ \(0\) đến \(100\) cộng dồn tần suất cho tới khi vượt qua mốc giữatotal / 2(tối đa \(101\) bước lặp, tức \(O(1)\) thời gian và \(O(1)\) bộ nhớ bất kể luồng có hàng tỷ phần tử).
- Trả lời: Thay vì dùng hai Heap tốn bộ nhớ \(O(n)\) và thời gian \(O(\log n)\), ta chỉ cần khai báo một mảng đếm tần suất cố định
- Câu hỏi mở rộng 2: "Nếu \(99\%\) các số nằm trong đoạn \([0, 100]\), nhưng có \(1\%\) các số ngoại lai nhỏ hơn \(0\) hoặc lớn hơn \(100\) thì sao?"
- Trả lời: Vì trung vị luôn nằm ở vị trí \(50\%\) chính giữa, còn tổng số phần tử ngoại lai ở hai đầu chỉ chiếm \(1\%\) (\(\ll 50\%\)), nên trung vị chắc chắn vẫn luôn rơi vào trong đoạn \([0, 100]\)! Ta chỉ cần giữ nguyên mảng đếm
cnt[0..100]kèm thêm hai biến đếm số nguyên đơn giản:less_than_zero(đếm các số \(\lt 0\)) vàgreater_than_100(đếm các số \(\gt 100\)). Khi tìm phần tử thứ \(k = \text{total} / 2\), ta khởi đầu biến cộng dồn bằngless_than_zerorồi quét quacnt[0..100]như câu 1 (nếu đề bài nói tỉ lệ ngoại lai có thể vượt \(50\%\) ở những bước đầu tiên khi \(n\) còn nhỏ, ta dùng haimultiset/Heap nhỏ chỉ để giữ phần ngoại lai).
- Trả lời: Vì trung vị luôn nằm ở vị trí \(50\%\) chính giữa, còn tổng số phần tử ngoại lai ở hai đầu chỉ chiếm \(1\%\) (\(\ll 50\%\)), nên trung vị chắc chắn vẫn luôn rơi vào trong đoạn \([0, 100]\)! Ta chỉ cần giữ nguyên mảng đếm
Luyện ngay trên Big-O Coding
Để thành thạo cách phối hợp nhiều hàng đợi ưu tiên trong các bài toán luồng dữ liệu và điều phối tác vụ, bạn hãy luyện tập ngay bộ ba bài toán dưới đây trong lộ trình Coding Interview 150:
Làm thế nào để mở rộng bài toán sang Trung vị trên cửa sổ trượt (Sliding Window Median — LeetCode 480)?
Khi cửa sổ trượt kích thước \(k\) dịch chuyển, ngoài việc thêm phần tử mới nums[i], ta còn phải xóa phần tử cũ nums[i - k] vừa rơi ra ngoài cửa sổ. Vì Heap chuẩn không hỗ trợ xóa một phần tử bất kỳ ở lưng chừng trong \(O(\log k)\), ta sử dụng kỹ thuật Xóa lười (Lazy Deletion):
- Duy trì hai biến đếm số phần tử hợp lệ thực sự (
valid_lowervàvalid_upper) thay vì dùng.size()vật lý của Heap. - Khi một phần tử
out_valbị trượt ra khỏi cửa sổ, ta chỉ giảmvalid_lower--(nếu \(\text{out\_val} \le \text{lower.top()}\)) hoặcvalid_upper--(nếu ngược lại), đồng thời ghi nhậndelayed[out_val]++vào một bảng băm. - Sau khi cân bằng lại hai Heap theo
valid_lowervàvalid_upper, ta mới kiểm tra đỉnh của hai Heap: chừng nào phần tử nằm ngay trên đỉnhtop()códelayed[top] > 0, ta gọipop()thật và giảmdelayed[top]--. Nhờ chỉ xóa khi phần tử lỗi thời trồi lên đỉnh, mỗi bước trượt cửa sổ vẫn chạy trong \(O(\log k)\) trung bình.
Tại sao ta quy ước cho lower giữ nhiều hơn upper tối đa 1 phần tử mà không làm ngược lại?
Đây hoàn toàn là quy ước đối xứng để thống nhất code. Nếu bạn quy ước \(|\text{lower}| \ge |\text{upper}|\), khi tổng số phần tử lẻ thì trung vị nằm ở lower.top(). Nếu bạn đảo ngược thứ tự đẩy trong addNum (đẩy vào upper trước \(\to\) chuyển sang lower \(\to\) nếu \(|\text{lower}| \gt |\text{upper}|\) thì trả về upper), khi đó \(|\text{upper}| \ge |\text{lower}|\) và trung vị khi tổng lẻ sẽ nằm ở upper.top(). Cả hai cách đều đúng 100%, chỉ cần nhất quán giữa bước cân bằng trong addNum và bước đọc đỉnh trong findMedian.
Trong C++, dùng một std::multiset<int> kèm một iterator trỏ vào phần tử giữa có tốt hơn dùng hai priority_queue không?
Về mặt độ phức tạp lý thuyết, cả hai đều tốn \(O(\log n)\) khi chèn và \(O(1)\) khi đọc trung vị. Tuy nhiên, trên thực tế thực thi, std::priority_queue được cài đặt trên nền mảng động liên tiếp (std::vector) nên có tính cục bộ bộ nhớ đệm CPU (cache locality) rất cao và không tốn chi phí cấp phát từng nút rời rạc kèm 3 con trỏ cha - trái - phải như cây đỏ đen (std::multiset). Vì vậy, hai priority_queue thường chạy nhanh hơn từ \(3\) đến \(5\) lần so với multiset trên luồng dữ liệu lớn.
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.


