ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็มและจำนวนเต็ม K หน้าที่ของเราคือสร้างโปรแกรมที่จะค้นหาองค์ประกอบที่ไม่ซ้ำกันสูงสุดในทุกอาร์เรย์ย่อยของขนาด K โดยไม่มีรายการซ้ำ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล −
array = {4, 1, 1, 3, 3}
k = 3 ผลผลิต −
4 3 1
คำอธิบาย −
Sub-array of size 3
Subarray {4, 1, 1}, max = 4
Subarray {1, 1, 3}, max = 3
Subarray {1, 3, 3}, max = 1 ในการแก้ปัญหานี้ วิธีง่ายๆ วิธีหนึ่งคือการเรียกใช้สองลูปและสร้างอาร์เรย์ย่อยและค้นหาองค์ประกอบที่แตกต่างกันและพิมพ์ให้ได้มากที่สุด
แต่วิธีแก้ไขที่มีประสิทธิภาพคือการใช้ วิธีหน้าต่างบานเลื่อน ใช้ตารางแฮชและ BST ที่สมดุลในตัวเองเพื่อค้นหาองค์ประกอบสูงสุด
ดังนั้น เราจะสำรวจอาร์เรย์ และสำหรับสรุปความยาว k ให้เก็บการนับองค์ประกอบในตารางแฮช และเก็บองค์ประกอบในชุด (ซึ่งจะเก็บเฉพาะองค์ประกอบที่ไม่ซ้ำ) และพิมพ์ค่าสูงสุดของชุดและทำเช่นเดียวกันกับการวนซ้ำทุกครั้งในอาร์เรย์
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The maximum unique element for a subarray of size 4 is 4 -1 5
