Phần tử duy nhất lớn nhất trong mọi mảng con kích thước K trong C++

Trong bài toán này, chúng ta được cho một mảng số nguyên và một số nguyên K. Nhiệm vụ là tạo một chương trình tìm phần tử duy nhất lớn nhất trong mọi mảng con kích thước K không có phần tử trùng lặp.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào –

mảng = {4, 1, 1, 3, 3} k = 3

Đầu ra –

4 3 1

Giải thích –

Mảng con kích thước 3:
Mảng con {4, 1, 1}, max = 4
Mảng con {1, 1, 3}, max = 3
Mảng con {1, 3, 3}, max = 1

Để giải quyết bài toán này, một phương pháp đơn giản là chạy hai vòng lặp tạo mảng con và tìm các phần tử riêng biệt và in max của chúng.

Nhưng một giải pháp hiệu quả là sử dụng phương pháp cửa sổ trượt sử dụng bảng băm và BST tự cân bằng để tìm các phần tử lớn nhất.

Vì vậy, chúng ta sẽ duyệt mảng và với tóm tắt độ dài k lưu trữ số lần xuất hiện của các phần tử trong bảng băm và lưu các phần tử trong một set (chỉ lưu các phần tử duy nhất). Và in max của set và làm tương tự cho mọi lần lặp trong mảng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp:

#include <bits/stdc++.h>
using namespace std;
void maxUniqueSubArrayElement(int A[], int N, int K){
    map<int, int> eleCount;
    for (int i = 0; i < K - 1; i++)
        eleCount[A[i]]++;
    set<int> uniqueMax;
    for (auto x : eleCount)
        if (x.second == 1)
            uniqueMax.insert(x.first);
    for (int i = K - 1; i < N; i++) {
        eleCount[A[i]]++;
        if (eleCount[A[i]] == 1)
            uniqueMax.insert(A[i]);
        else
            uniqueMax.erase(A[i]);
        if (uniqueMax.size() == 0)
            cout<<"-1\t" ;
        else
            cout<<*uniqueMax.rbegin()<<"\t";
        int x = A[i - K + 1];
        eleCount[x]--;
        if (eleCount[x] == 1)
            uniqueMax.insert(x);
        if (eleCount[x] == 0)
            uniqueMax.erase(x);
    }
}
int main(){
    int a[] = { 4, 3, 2, 2, 3, 5};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 4;
    cout<<"Phần tử duy nhất lớn nhất cho mảng con kích thước "<<k<<" là\n";
    maxUniqueSubArrayElement(a, n, k);
    return 0;
}

Kết quả

Phần tử duy nhất lớn nhất cho mảng con kích thước 4 là 4 -1 5