Bài học

Duyệt mảng: tìm max, min, tổng và biến thể

Mục tiêu bài học

Sau bài này, em duyệt một mảng đúng một lượt để tìm giá trị lớn nhất, giá trị lớn thứ hai, hoặc giá trị xuất hiện nhiều nhất — không sắp xếp trước, không duyệt lại từ đầu. Đây là kỹ năng nền của gần như mọi bài toán mảng ở các bài sau.

Cần nhớ trước

Em cần nhớ: cú pháp for duyệt list trong Python, cách viết hàm nhận list làm tham số, và cách đếm số vòng lặp thực thi để ước lượng độ phức tạp O(n)/O(n²) đã học ở khóa trước.

So với mức chuẩn: đề chuẩn Lớp 10 thường chỉ yêu cầu in ra từng phần tử của một list, hoặc dùng max()/min()/sum() có sẵn của Python. Đề HSG đi xa hơn: hỏi những đại lượng mà Python không có hàm dựng sẵn nào tính thẳng được — vị trí của giá trị lớn nhất, giá trị lớn thứ hai, giá trị xuất hiện nhiều nhất — và thường cấm duyệt mảng quá một lần vì lý do hiệu năng.

**So với mức chuẩn:** đề chuẩn Lớp 10 thường chỉ yêu cầu in ra từng phần tử của một list, hoặc dùng `max()`/`min()`/`sum()` có sẵn của Python. Đề HSG đi xa hơn: hỏi những đại lượng mà Python không có hàm dựng sẵn nào tính thẳng được — vị trí của giá trị lớn nhất, giá trị lớn thứ hai, giá trị xuất hiện nhiều nhất — và thường cấm duyệt mảng quá một lần vì lý do hiệu năng.

Mở rộng dành cho HSG

Mở rộng dành cho HSG: trước khi đặt bút viết vòng lặp, luôn tự hỏi "bài này có cần duyệt mảng hai lần không, hay một lượt là đủ?". Duyệt một lượt (single pass) là kỹ thuật nền cho hầu hết bài thống kê mảng trong đề HSG — vượt khỏi yêu cầu chuẩn của Lớp 10, vốn chỉ dừng ở việc gọi hàm dựng sẵn.

Bài toán mở đầu — khi hàm dựng sẵn không đủ

Cho mảng điểm [4, 9, 2, 12]. Đề chuẩn chỉ hỏi giá trị lớn nhất — max(a) trả lời ngay. Đề HSG hỏi thêm: giá trị lớn nhất nằm ở VỊ TRÍ nào? Giá trị lớn thứ hai là bao nhiêu, mà không được sắp xếp mảng? Cả hai câu hỏi này max() không trả lời được — em phải tự duyệt và tự ghi nhớ đúng những gì mình cần.

Cho mảng điểm `[4, 9, 2, 12]`. Đề chuẩn chỉ hỏi giá trị lớn nhất — `max(a)` trả lời ngay. Đề HSG hỏi thêm: giá trị lớn nhất nằm ở VỊ TRÍ nào? Giá trị lớn thứ hai là bao nhiêu, mà không được sắp xếp mảng? Cả hai câu hỏi này `max()` không trả lời được — em phải tự duyệt và tự ghi nhớ đúng những gì mình cần.

Ý tưởng cốt lõi — giữ đúng biến mình cần, cập nhật khi có cơ hội

Nguyên tắc chung của duyệt một lượt: chọn một hoặc vài biến đại diện cho "trạng thái tốt nhất tính đến vị trí hiện tại", rồi duyệt qua từng phần tử đúng một lần — mỗi phần tử chỉ có thể làm một việc: cập nhật trạng thái đó, hoặc bị bỏ qua vì không tốt hơn. Không có phần tử nào cần xét lại lần thứ hai.

Ví dụ

Ví dụ 1 — Tìm giá trị lớn nhất và vị trí của nó

1
Đề chuẩn chỉ hỏi max(a). Ở đây đề hỏi thêm VỊ TRÍ của giá trị lớn nhất — thông tin max() không trả về, buộc em phải tự duyệt và tự ghi nhớ chỉ số đi kèm giá trị.
2
Khởi tạo best = a[0], best_idx = 0. Duyệt tiếp từ chỉ số $1$ : nếu a[i] > best thì cập nhật cả best lẫn best_idx. Sau khi duyệt hết mảng, hai biến này chính là đáp án.
Khởi tạo `best = a[0]`, `best_idx = 0`. Duyệt tiếp từ chỉ số $1$: nếu `a[i] > best` thì cập nhật cả `best` lẫn `best_idx`. Sau khi duyệt hết mảng, hai biến này chính là đáp án.
3
Ta có bất biến: ngay sau khi xét xong chỉ số $i$ , best luôn bằng giá trị lớn nhất trong $a[0..i]$ . Bất biến đúng ngay khi khởi tạo ( $i=0$ ), và mỗi lần cập nhật giữ bất biến đúng cho $i+1$ . Khi $i$ chạy hết mảng, bất biến cho ta đúng đáp án trên toàn mảng — đây gọi là chứng minh bằng quy nạp.
Ta có bất biến: ngay sau khi xét xong chỉ số $i$, `best` luôn bằng giá trị lớn nhất trong $a[0..i]$. Bất biến đúng ngay khi khởi tạo ($i=0$), và mỗi lần cập nhật giữ bất biến đúng cho $i+1$. Khi $i$ chạy hết mảng, bất biến cho ta đúng đáp án trên toàn mảng — đây gọi là chứng minh bằng quy nạp.

def tim_max_va_vi_tri(a):
    """Duyet mot luot, tra ve (gia_tri_lon_nhat, vi_tri) cua mang a."""
    if not a:
        raise ValueError("mang rong khong co gia tri lon nhat")
    best = a[0]
    best_idx = 0
    for i in range(1, len(a)):
        if a[i] > best:
            best = a[i]
            best_idx = i
    return best, best_idx

5
Với a = [4, 9, 2, 12]: best khởi tạo $= a[0] = 4$ . Xét $i=1$ : $a[1]=9>4$ nên cập nhật best=9, best_idx=1. Xét $i=2$ : $a[2]=2$ không lớn hơn $9$ , bỏ qua. Xét $i=3$ : $a[3]=12>9$ nên cập nhật best=12, best_idx=3. Kết quả tim_max_va_vi_tri([4, 9, 2, 12]) = (12, 3) — đã chạy và khớp bằng assert trước khi đưa vào bài này.
Với `a = [4, 9, 2, 12]`: `best` khởi tạo $= a[0] = 4$. Xét $i=1$: $a[1]=9>4$ nên cập nhật `best=9`, `best_idx=1`. Xét $i=2$: $a[2]=2$ không lớn hơn $9$, bỏ qua. Xét $i=3$: $a[3]=12>9$ nên cập nhật `best=12`, `best_idx=3`. Kết quả `tim_max_va_vi_tri([4, 9, 2, 12])` = `(12, 3)` — đã chạy và khớp bằng `assert` trước khi đưa vào bài này.
6
Thuật toán chỉ duyệt mảng đúng một lần, mỗi phần tử làm đúng một phép so sánh — độ phức tạp $O(n)$ , không cần bộ nhớ phụ. Biến thể: muốn tìm GIÁ TRỊ NHỎ NHẤT thì đổi dấu so sánh từ > thành <; muốn tìm cả hai cùng lúc thì giữ hai cặp biến song song trong cùng một lượt duyệt.
Thuật toán chỉ duyệt mảng đúng một lần, mỗi phần tử làm đúng một phép so sánh — độ phức tạp $O(n)$, không cần bộ nhớ phụ. Biến thể: muốn tìm GIÁ TRỊ NHỎ NHẤT thì đổi dấu so sánh từ `>` thành `<`; muốn tìm cả hai cùng lúc thì giữ hai cặp biến song song trong cùng một lượt duyệt.
7
Ta có best khởi tạo bằng $a[0]=4$ , best_idx=0. Xét lần lượt $a[1], a[2], a[3]$ : best chỉ cập nhật khi gặp giá trị lớn hơn best hiện tại, tức tại $i=1$ (thành $9$ ) và $i=3$ (thành $12$ ). Không còn phần tử nào lớn hơn $12$ sau đó. Vậy giá trị lớn nhất của mảng là $12$ , tại vị trí $3$ .
Ta có `best` khởi tạo bằng $a[0]=4$, `best_idx=0`. Xét lần lượt $a[1], a[2], a[3]$: `best` chỉ cập nhật khi gặp giá trị lớn hơn `best` hiện tại, tức tại $i=1$ (thành $9$) và $i=3$ (thành $12$). Không còn phần tử nào lớn hơn $12$ sau đó. Vậy giá trị lớn nhất của mảng là $12$, tại vị trí $3$.

Bước 0: a[0]=4 → best=4, best_idx=0 (khởi tạo)

Bước 1: a[1]=9 > 4 → cập nhật best=9, best_idx=1

Bước 2: a[2]=2 không lớn hơn 9 → giữ nguyên best=9

Bước 3: a[3]=12 > 9 → cập nhật best=12, best_idx=3 (kết quả cuối)

Khuôn mẫu chung cho mọi bài thống kê mảng bằng một lượt duyệt — chỉ khác nhau ở điều kiện cập nhật.

Ví dụ

Ví dụ 2 — Tìm giá trị lớn thứ hai, không sắp xếp

1
Đề chuẩn không hỏi "lớn thứ hai". Cách làm ngây thơ là sorted(a)[-2], tốn $O(n\log n)$ và còn SAI nếu giá trị lớn nhất xuất hiện nhiều lần — khi đó sorted(a)[-2] vẫn bằng giá trị lớn nhất, không phải giá trị lớn thứ hai thật sự.
Đề chuẩn không hỏi "lớn thứ hai". Cách làm ngây thơ là `sorted(a)[-2]`, tốn $O(n\log n)$ và còn SAI nếu giá trị lớn nhất xuất hiện nhiều lần — khi đó `sorted(a)[-2]` vẫn bằng giá trị lớn nhất, không phải giá trị lớn thứ hai thật sự.
2
Giữ hai biến nhat và nhi. Mỗi phần tử mới chỉ có ba khả năng: lớn hơn nhat (nó trở thành nhat mới, nhat cũ tụt xuống làm nhi); nằm chặt giữa nhat và nhi (nó trở thành nhi mới); hoặc không lớn hơn nhi (bỏ qua). Không còn khả năng nào khác, nên một lượt duyệt là đủ.
Giữ hai biến `nhat` và `nhi`. Mỗi phần tử mới chỉ có ba khả năng: lớn hơn `nhat` (nó trở thành `nhat` mới, `nhat` cũ tụt xuống làm `nhi`); nằm chặt giữa `nhat` và `nhi` (nó trở thành `nhi` mới); hoặc không lớn hơn `nhi` (bỏ qua). Không còn khả năng nào khác, nên một lượt duyệt là đủ.
3
Bất biến: sau khi xét xong một phần tử, nhat luôn là giá trị lớn nhất và nhi luôn là giá trị lớn thứ hai PHÂN BIỆT trong phần mảng đã xét. Điều kiện nhat > x > nhi (chứ không phải >=) đảm bảo một giá trị trùng với nhat không bao giờ bị hiểu nhầm thành "giá trị lớn thứ hai".
Bất biến: sau khi xét xong một phần tử, `nhat` luôn là giá trị lớn nhất và `nhi` luôn là giá trị lớn thứ hai PHÂN BIỆT trong phần mảng đã xét. Điều kiện `nhat > x > nhi` (chứ không phải `>=`) đảm bảo một giá trị trùng với `nhat` không bao giờ bị hiểu nhầm thành "giá trị lớn thứ hai".
4
```
def tim_lon_thu_hai(a):
    """Gia tri lon thu hai, PHAN BIET voi gia tri lon nhat.
    Tra ve None neu mang khong co du hai gia tri phan biet."""
    nhat = nhi = float("-inf")
    for x in a:
        if x > nhat:
            nhi = nhat
            nhat = x
        elif nhat > x > nhi:
            nhi = x
    return None if nhi == float("-inf") else nhi
```
```python def tim_lon_thu_hai(a): """Gia tri lon thu hai, PHAN BIET voi gia tri lon nhat. Tra ve None neu mang khong co du hai gia tri phan biet.""" nhat = nhi = float("-inf") for x in a: if x > nhat: nhi = nhat nhat = x elif nhat > x > nhi: nhi = x return None if nhi == float("-inf") else nhi ```
5
Với a = [4, 9, 2, 12, 5]: sau khi xét $4$ và $9$ , nhat=9, nhi=4. Xét $2$ : không thỏa $9>2>4$ , bỏ qua. Xét $12$ : lớn hơn nhat, nên nhi nhận giá trị nhat cũ là $9$ , nhat thành $12$ . Xét $5$ : không thỏa $12>5>9$ , bỏ qua. Kết quả tim_lon_thu_hai([4, 9, 2, 12, 5]) = 9.
Với `a = [4, 9, 2, 12, 5]`: sau khi xét $4$ và $9$, `nhat=9`, `nhi=4`. Xét $2$: không thỏa $9>2>4$, bỏ qua. Xét $12$: lớn hơn `nhat`, nên `nhi` nhận giá trị `nhat` cũ là $9$, `nhat` thành $12$. Xét $5$: không thỏa $12>5>9$, bỏ qua. Kết quả `tim_lon_thu_hai([4, 9, 2, 12, 5])` = `9`.
6
Vẫn $O(n)$ thời gian, $O(1)$ bộ nhớ phụ — nhanh hơn hẳn cách sắp xếp rồi lấy a[-2]. Biến thể: nếu mảng toàn giá trị bằng nhau, hoặc chỉ có $0$ hay $1$ phần tử, hàm trả về None vì không tồn tại giá trị lớn thứ hai phân biệt — luôn kiểm tra None trước khi dùng kết quả.
Vẫn $O(n)$ thời gian, $O(1)$ bộ nhớ phụ — nhanh hơn hẳn cách sắp xếp rồi lấy `a[-2]`. Biến thể: nếu mảng toàn giá trị bằng nhau, hoặc chỉ có $0$ hay $1$ phần tử, hàm trả về `None` vì không tồn tại giá trị lớn thứ hai phân biệt — luôn kiểm tra `None` trước khi dùng kết quả.
7
Ta duyệt [4, 9, 2, 12, 5] và cập nhật cặp (nhat, nhi) theo quy tắc trên. Giá trị lớn nhất là $12$ (tại phần tử thứ tư); trong số các giá trị còn lại, giá trị lớn nhất là $9$ . Vậy giá trị lớn thứ hai của mảng là $9$ .
Ta duyệt `[4, 9, 2, 12, 5]` và cập nhật cặp (`nhat`, `nhi`) theo quy tắc trên. Giá trị lớn nhất là $12$ (tại phần tử thứ tư); trong số các giá trị còn lại, giá trị lớn nhất là $9$. Vậy giá trị lớn thứ hai của mảng là $9$.

Bẫy thường gặp

Ba lỗi hay gặp: dùng >= thay vì > khi so sánh với nhi, khiến một phần tử bằng nhat bị tính nhầm thành "lớn thứ hai"; quên kiểm tra None khi mảng có ít hơn hai giá trị phân biệt; và tưởng rằng cứ duyệt hai lần là luôn chậm hơn — thực ra hai lượt duyệt độc lập vẫn là $O(n)$ , chỉ là không cần thiết ở bài này.

Ba lỗi hay gặp: dùng `>=` thay vì `>` khi so sánh với `nhi`, khiến một phần tử bằng `nhat` bị tính nhầm thành "lớn thứ hai"; quên kiểm tra `None` khi mảng có ít hơn hai giá trị phân biệt; và tưởng rằng cứ duyệt hai lần là luôn chậm hơn — thực ra hai lượt duyệt độc lập vẫn là $O(n)$, chỉ là không cần thiết ở bài này.

Ví dụ

Ví dụ 3 — Giá trị xuất hiện nhiều nhất trong mảng nhỏ

1
Đề chuẩn chỉ đếm số lần xuất hiện của MỘT giá trị cho trước. Ở đây đề hỏi giá trị nào xuất hiện nhiều nhất — em không biết trước cần đếm giá trị nào, nên phải đếm đồng thời tần suất của mọi giá trị xuất hiện trong mảng.
2
Dùng một dict để đếm tần suất: duyệt mảng một lượt, mỗi phần tử x thì tăng dem[x] lên $1$ . Sau đó duyệt lại mảng (theo đúng thứ tự gốc) để tìm giá trị có dem[x] lớn nhất — duyệt theo thứ tự gốc đảm bảo hòa thì chọn giá trị xuất hiện sớm nhất, một quy tắc hòa rõ ràng thay vì tùy tiện.
Dùng một `dict` để đếm tần suất: duyệt mảng một lượt, mỗi phần tử `x` thì tăng `dem[x]` lên $1$. Sau đó duyệt lại mảng (theo đúng thứ tự gốc) để tìm giá trị có `dem[x]` lớn nhất — duyệt theo thứ tự gốc đảm bảo hòa thì chọn giá trị xuất hiện sớm nhất, một quy tắc hòa rõ ràng thay vì tùy tiện.
3
Sau bước một, dem[x] là tần suất THẬT của $x$ trên toàn mảng — không phụ thuộc thứ tự đếm. Bước hai chỉ chọn giá trị lớn nhất trong các dem[x] đó, dùng đúng khuôn mẫu duyệt một lượt của Ví dụ 1.
Sau bước một, `dem[x]` là tần suất THẬT của $x$ trên toàn mảng — không phụ thuộc thứ tự đếm. Bước hai chỉ chọn giá trị lớn nhất trong các `dem[x]` đó, dùng đúng khuôn mẫu duyệt một lượt của Ví dụ 1.
4
```
def gia_tri_xuat_hien_nhieu_nhat(a):
    """(gia_tri, so_lan) xuat hien nhieu nhat; hoa thi lay gia tri xuat
    hien SOM NHAT trong mang. Tra ve None neu mang rong."""
    if not a:
        return None
    dem = {}
    for x in a:
        dem[x] = dem.get(x, 0) + 1
    best_val, best_dem = a[0], 0
    for x in a:
        if dem[x] > best_dem:
            best_val, best_dem = x, dem[x]
    return best_val, best_dem
```
```python def gia_tri_xuat_hien_nhieu_nhat(a): """(gia_tri, so_lan) xuat hien nhieu nhat; hoa thi lay gia tri xuat hien SOM NHAT trong mang. Tra ve None neu mang rong.""" if not a: return None dem = {} for x in a: dem[x] = dem.get(x, 0) + 1 best_val, best_dem = a[0], 0 for x in a: if dem[x] > best_dem: best_val, best_dem = x, dem[x] return best_val, best_dem ```
5
Với a = [2, 5, 2, 8, 5, 2]: tần suất là {2: 3, 5: 2, 8: 1}. Giá trị $2$ có tần suất lớn nhất. Kết quả gia_tri_xuat_hien_nhieu_nhat([2, 5, 2, 8, 5, 2]) = (2, 3).
Với `a = [2, 5, 2, 8, 5, 2]`: tần suất là `{2: 3, 5: 2, 8: 1}`. Giá trị $2$ có tần suất lớn nhất. Kết quả `gia_tri_xuat_hien_nhieu_nhat([2, 5, 2, 8, 5, 2])` = `(2, 3)`.
6
Hai lượt duyệt độc lập vẫn là $O(n)$ thời gian, tốn thêm $O(k)$ bộ nhớ cho dict với $k$ là số giá trị phân biệt. Biến thể: nếu đề chỉ cần TẦN SUẤT lớn nhất chứ không cần giá trị, có thể dùng max(dem.values()) sau bước đếm.
Hai lượt duyệt độc lập vẫn là $O(n)$ thời gian, tốn thêm $O(k)$ bộ nhớ cho `dict` với $k$ là số giá trị phân biệt. Biến thể: nếu đề chỉ cần TẦN SUẤT lớn nhất chứ không cần giá trị, có thể dùng `max(dem.values())` sau bước đếm.
7
Đếm tần suất từng giá trị trong [2, 5, 2, 8, 5, 2] bằng dict, ta được $2$ xuất hiện $3$ lần — nhiều hơn mọi giá trị khác. Vậy giá trị xuất hiện nhiều nhất là $2$ , với tần suất $3$ .
Đếm tần suất từng giá trị trong `[2, 5, 2, 8, 5, 2]` bằng `dict`, ta được $2$ xuất hiện $3$ lần — nhiều hơn mọi giá trị khác. Vậy giá trị xuất hiện nhiều nhất là $2$, với tần suất $3$.

Luyện tập có hướng dẫn

Luyện tập độc lập

Thử thách

Tóm tắt

Duyệt một lượt là kỹ thuật giữ một (hoặc vài) biến trạng thái và cập nhật chúng khi gặp phần tử tốt hơn — dùng được cho tìm max/min, tìm giá trị lớn thứ hai, hay đếm tần suất, tất cả đều $O(n)$ và không cần sắp xếp. Trước khi viết vòng lặp thứ hai, luôn tự hỏi liệu một lượt duyệt có đủ hay không.

Bài sau đi từ thống kê MỘT giá trị sang thống kê một ĐOẠN mảng liên tiếp: tổng đoạn con lớn nhất, và kỹ thuật tổng tiền tố giúp trả lời nhiều truy vấn tổng đoạn mà không cần tính lại từ đầu mỗi lần.