Trong bài toán này, chúng ta được cung cấp một mảng các số nguyên và một số nguyên K. Nhiệm vụ của chúng ta là tạo một chương trình sẽ tìm phần tử duy nhất tối đa trong mọi mảng con có kích thước K mà không có bản sao.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào -
array = {4, 1, 1, 3, 3}
k = 3 Đầu ra -
4 3 1
Giải thích -
Sub-array of size 3
Subarray {4, 1, 1}, max = 4
Subarray {1, 1, 3}, max = 3
Subarray {1, 3, 3}, max = 1 Để giải quyết vấn đề này, một phương pháp đơn giản là chạy hai vòng lặp và tạo các mảng con, đồng thời tìm các phần tử riêng biệt và in ra tối đ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ử tối đa.
Vì vậy, chúng ta sẽ duyệt qua mảng và đối với tóm tắt độ dài k lưu trữ số lượng các phần tử trong bảng băm và lưu trữ các phần tử trong một tập hợp (sẽ chỉ lưu trữ các phần tử duy nhất). Và in giá trị tối đa của tập hợp và thực hiện 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 của chúng tôi,
#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<<"The maximum unique element for a subarray of size "<<k<<" is\n";
maxUniqueSubArrayElement(a, n, k);
return 0;
} Đầu ra
The maximum unique element for a subarray of size 4 is 4 -1 5