Hiểu bài toán

Cho một mảng gồm N phần tử (1 ≤ N ≤ 1000), nhiệm vụ của bạn là tìm và in ra 3 số lớn nhất trong mảng theo thứ tự giảm dần (lớn nhất trước, thứ hai sau, thứ ba cuối cùng). Ví dụ, với mảng [1, 2, 3, 4, 5], output mong đợi là 5, 4, 3.

Các cách tiếp cận

Cách Sắp xếp mảng (Sorting)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.rbegin(), a.rend()); // Sắp xếp giảm dần
    cout << a[0] << endl << a[1] << endl << a[2] << endl;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Phương pháp này đọc toàn bộ dữ liệu vào mảng, sau đó sử dụng hàm sort với iterators đảo ngược (rbegin, rend) để sắp xếp mảng theo thứ tự giảm dần. Sau đó, chỉ cần in ra 3 phần tử đầu tiên của mảng (chỉ số 0, 1, 2). Đây là cách tiếp cận đơn giản nhất, dễ hiểu và dễ cài đặt, phù hợp với ràng buộc N nhỏ (N ≤ 1000).

Cách Duyệt một lần (One Pass)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
    for (int x : a) {
        if (x > m1) {
            m3 = m2;
            m2 = m1;
            m1 = x;
        } else if (x > m2) {
            m3 = m2;
            m2 = x;
        } else if (x > m3) {
            m3 = x;
        }
    }
    cout << m1 << '\n' << m2 << '\n' << m3;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là phương pháp tối ưu về mặt thời gian. Chúng ta sử dụng 3 biến m1, m2, m3 để lưu trữ 3 số lớn nhất tìm được cho đến hiện tại. Duyệt qua từng phần tử trong mảng:

1. Nếu phần tử hiện tại lớn hơn m1, ta đẩy m1 xuống m2, m2 xuống m3 và gán phần tử hiện tại cho m1.
2. Nếu không lớn hơn m1 nhưng lớn hơn m2, ta đẩy m2 xuống m3 và gán phần tử hiện tại cho m2.
3. Nếu chỉ lớn hơn m3, ta cập nhật m3. Phương pháp này chỉ cần duyệt qua mảng đúng một lần, rất hiệu quả.

Cách Lưu trữ toàn bộ và truy cập theo chỉ số

#include <bits/stdc++.h>
using namespace std;
int a[100009];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1); // Sắp xếp tăng dần
    cout << a[n] << "\n" << a[n - 1] << "\n" << a[n - 2];
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Giống như cách tiếp cận đầu tiên, phương pháp này cũng sử dụng sắp xếp. Tuy nhiên, nó sử dụng mảng tĩnh và sắp xếp theo thứ tự tăng dần mặc định. Do đó, 3 số lớn nhất sẽ nằm ở cuối mảng (chỉ số n, n-1, n-2 nếu dùng mảng đánh dấu từ 1). Logic này tương tự cách 1 nhưng khác biệt về thứ tự sắp xếp và cách truy cập phần tử.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Với ràng buộc N nhỏ (≤ 1000), việc sử dụng hàm sort có sẵn là cách nhanh nhất để cài đặt (viết ít code) và đủ nhanh về tốc độ.
• Nếu N rất lớn (ví dụ 10^7), việc sắp xếp toàn bộ mảng là lãng phí. Khi đó, phương pháp dùng 3 biến (One Pass) là tối ưu nhất với độ phức tạp O(N) và bộ nhớ O(1).
• Cần phân biệt rõ giữa sort(a.begin(), a.end()) (tăng dần) và sort(a.rbegin(), a.rend()) (giảm dần) hoặc cách tính toán chỉ số khi mảng tăng dần.

Lỗi thường gặp

• Lỗi chỉ số mảng (Off-by-one error): Khi in 3 số lớn nhất, nếu mảng tăng dần, phải in a[n-1], a[n-2], a[n-3] (nếu đánh dấu từ 0). Cần cẩn thận với việc đánh dấu chỉ số của mảng.
• Khởi tạo giá trị ban đầu: Trong phương pháp dùng 3 biến, nếu khởi tạo các biến bằng 0 trong khi dữ liệu input có thể âm (mặc dù đề bài này a_i ≥ 1), kết quả sẽ sai. Nên dùng INT_MIN hoặc giá trị nhỏ nhất của bài toán.
• Xử lý số phần tử nhỏ hơn 3: Đề bài cho N ≥ 1, nhưng không rõ N có thể nhỏ hơn 3 hay không. Nếu N < 3, chương trình có thể truy cập ra ngoài mảng (Segmentation Fault) nếu không kiểm tra điều kiện.