Hiểu bài toán

Bài toán yêu cầu tìm phần tử thứ K lớn nhất (hoặc nhỏ nhất tùy ngữ cảnh, nhưng ở đây là phần tử thứ K lớn nhất) trong một dãy số khi duyệt tuần tự. Cụ thể, với N phần tử và một chỉ số K, ta cần in ra giá trị phần tử thứ K lớn nhất trong đoạn đầu tiên gồm K phần tử, sau đó với mỗi phần tử tiếp theo được thêm vào dãy, ta phải in ra phần tử thứ K lớn nhất của dãy hiện tại (bao gồm K+1, K+2, ... phần tử).

Ví dụ: Input: N=5, K=3, dãy A = [1, 5, 2, 4, 3].

• Bước 1 (3 phần tử đầu: 1, 5, 2): Sắp xếp giảm dần [5, 2, 1], phần tử thứ 3 là 2. In ra 2.
• Bước 2 (thêm 4): Dãy [1, 5, 2, 4]. Sắp xếp giảm dần [5, 4, 2, 1], phần tử thứ 3 là 4. In ra 4.
• Bước 3 (thêm 3): Dãy [1, 5, 2, 4, 3]. Sắp xếp giảm dần [5, 4, 3, 2, 1], phần tử thứ 3 là 3. In ra 3.

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

Cách Sử dụng Min-Heap (Priority Queue)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int n, K;
    cin >> n >> K;
    vector<int> P(n);
    for (int i = 0; i < n; ++i) {
        cin >> P[i];
    }

    // Min-Heap lưu K phần tử lớn nhất hiện tại
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Xử lý K phần tử đầu tiên
    for (int i = 0; i < K; ++i) {
        minHeap.push(P[i]);
    }
    cout << minHeap.top() << endl;

    // Duyệt các phần tử còn lại
    for (int i = K; i < n; ++i) {
        minHeap.push(P[i]);
        // Nếu Heap có nhiều hơn K phần tử, loại bỏ phần tử nhỏ nhất (đứng đầu Heap)
        if (minHeap.size() > K) {
            minHeap.pop();
        }
        // Phần tử nhỏ nhất trong K phần tử lớn nhất chính là phần tử thứ K
        cout << minHeap.top() << endl;
    }

    return 0;
}

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

Giải pháp này sử dụng một Min-Heap (đỉnh là phần tử nhỏ nhất) để lưu trữ K phần tử lớn nhất gặp được trong quá trình duyệt.

1. Khởi tạo: Duyệt K phần tử đầu tiên và thêm vào Heap.
2. Xử lý: Với mỗi phần tử mới từ vị trí K đến N-1:
   • Thêm phần tử vào Heap.
   • Nếu kích thước Heap vượt quá K, ta loại bỏ phần tử nhỏ nhất (sử dụng pop).
   • Lúc này, Heap luôn chứa chính xác K phần tử lớn nhất của dãy đã duyệt qua.
   • Giá trị tại đỉnh Heap (top) chính là phần tử nhỏ nhất trong K phần tử lớn nhất đó, tức là phần tử thứ K lớn nhất của toàn bộ dãy.

Độ phức tạp thời gian là O(N log K) do mỗi thao tác trên Heap mất O(log K) và ta thực hiện N lần. Độ phức tạp không gian là O(K) để lưu trữ Heap.

Cách Sử dụng Fenwick Tree (Binary Indexed Tree)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> bit;

// Cập nhật giá trị tại vị trí index
void update(int index, int delta) {
    for (; index <= N; index += index & (-index)) {
        bit[index] += delta;
    }
}

// Tính tổng tiền tố
int query(int index) {
    int sum = 0;
    for (; index > 0; index -= index & (-index)) {
        sum += bit[index];
    }
    return sum;
}

// Tìm kiếm nhị phân giá trị V nhỏ nhất sao cho query(V) >= target_count
int find_kth_largest(int target_count) {
    int low = 1;
    int high = N;
    int result = N;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int count = query(mid);
        if (count >= target_count) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Co valeurs để BIT hoạt động trên chỉ số 1..N
    // (Code mẫu mặc định dùng giá trị trực tiếp nếu giá trị <= N)
    bit.assign(N + 1, 0);

    // Xử lý K phần tử đầu tiên
    for (int i = 0; i < K; ++i) {
        update(A[i], 1);
    }
    cout << find_kth_largest(K) << endl;

    for (int i = K; i < N; ++i) {
        update(A[i], 1);       // Thêm phần tử mới
        update(A[i - K], -1);  // Loại bỏ phần tử cũ nhất
        cout << find_kth_largest(K) << endl;
    }
    return 0;
}

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

Giải pháp này sử dụng Fenwick Tree (BIT) để lưu tần suất các giá trị và thực hiện tìm kiếm nhị phân để tìm giá trị thứ K.

1. Cấu trúc dữ liệu: BIT lưu số lượng các phần tử có giá trị từ 1 đến X.
2. Logic:
   • Khi thêm một phần tử có giá trị x, ta cập nhật update(x, 1).
   • Khi loại bỏ một phần tử x, ta cập nhật update(x, -1).
   • Để tìm phần tử thứ K lớn nhất, ta cần tìm giá trị v sao cho có ít nhất K phần tử có giá trị >= v. Trong BIT (thường dùng cho tổng tiền tố), ta có thể chuyển đổi bài toán: tìm giá trị v sao cho tổng số phần tử có giá trị <= v là Total - K + 1 (nếu tìm phần tử thứ K nhỏ nhất) hoặc dùng tìm kiếm nhị phân trực tiếp trên BIT.
   • Trong code mẫu, hàm find_kth_largest thực hiện tìm kiếm nhị phân để tìm giá trị mid nhỏ nhất sao cho query(mid) >= target.
   • Lưu ý: Code mẫu trong submission gốc có vẻ chưa hoàn thiện hoàn toàn logic cho bài toán sliding window (chưa thấy đoạn loại bỏ phần tử cũ), nhưng cách tiếp cận BIT chung là như vậy.

Độ phức tạp: O(N log N) cho việc xử lý và tìm kiếm.

Cách Sử dụng Vector và Sắp xếp (Naive)

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

int main() {
    int n, k; 
    cin >> n >> k;
    vector <int> a(n);
    vector <int> v(0);
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i];
    }
    // Lấy k phần tử đầu
    for(int i = 0 ; i < k ; ++i){
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end(), greater<int> ());
    int solonthuk = v[k - 1];
    cout << solonthuk << '\n';

    // Duyệt tiếp và cập nhật
    for(int i = k ; i < n ; ++i){
        if(a[i] > solonthuk){
            auto it = lower_bound(v.begin(), v.end(), a[i], greater <int> ());
            v.insert(it, a[i]);
            v.pop_back();
            solonthuk = v[k - 1];
        }
        cout << solonthuk << '\n';
    }
    return 0;
}

• Time Complexity: O(N * K)
• Space Complexity: O(K)

Giải pháp này duy trì một vector chứa K phần tử lớn nhất và luôn giữ vector này được sắp xếp giảm dần.

1. Khởi tạo: Nhập K phần tử đầu tiên vào vector, sắp xếp giảm dần.
2. Xử lý: Với mỗi phần tử mới a[i]:
   • So sánh a[i] với phần tử nhỏ nhất trong danh sách K phần tử lớn nhất (solonthuk).
   • Nếu a[i] lớn hơn, ta cần chèn a[i] vào vị trí thích hợp trong vector đã sắp xếp (dùng lower_bound với comparator greater) và loại bỏ phần tử cuối cùng (phần tử nhỏ nhất).
   • Nếu không, danh sách không thay đổi.
   • In ra phần tử nhỏ nhất trong danh sách hiện tại.

Độ phức tạp: Việc chèn vào vector (insert) mất O(K). Trong trường hợp xấu nhất (dãy tăng dần), ta thực hiện chèn N-K lần, tổng độ phức tạp là O(N*K).

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

Bài học kinh nghiệm

• Bài toán có thể được coi là duy trì K phần tử lớn nhất trong một cửa sổ trượt (sliding window) có kích thước tăng dần.
• Min-Heap là cấu trúc dữ liệu phù hợp nhất cho bài toán này về mặt cân bằng giữa độ phức tạp thời gian và không gian.

Lỗi thường gặp

• Sử dụng Max-Heap thay vì Min-Heap: Nếu dùng Max-Heap, ta sẽ lưu tất cả các phần tử và loại bỏ các phần tử nhỏ nhất, điều này không hiệu quả. Phải dùng Min-Heap để lưu K phần tử lớn nhất.
• Quên trường hợp khi Heap/Vector chưa đủ K phần tử: Cần xử lý riêng K phần tử đầu tiên trước khi vào vòng lặp chính.
• Độ phức tạp không gian: Nếu dùng Max-Heap lưu tất cả phần tử, không gian có thể lên tới O(N), lãng phí.