องค์ประกอบที่ไม่ซ้ำกันสูงสุดในทุกซับอาร์เรย์ขนาด K ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็มและจำนวนเต็ม 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

ในการแก้ปัญหานี้ วิธีง่ายหนึ่งคือรันสองลูปและสร้างซับอาร์เรย์และหาองค์ประกอบที่แตกต่างกันและพิมพ์ค่าสูงสุดของพวกเขา

แต่วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้วิธี sliding window โดยใช้ hash table และ self-balancing BST เพื่อหาองค์ประกอบสูงสุด

ดังนั้น เราจะเดินทางผ่านอาร์เรย์ และสำหรับสรุปความยาว k จะเก็บจำนวนขององค์ประกอบใน hash table และเก็บองค์ประกอบใน set (ซึ่งจะเก็บเฉพาะองค์ประกอบที่ไม่ซ้ำกัน) และพิมพ์ค่าสูงสุดของ set และทำซ้ำสำหรับทุกการวนซ้ำในอาร์เรย์

ตัวอย่างโค้ด

โปรแกรมแสดงการทำงานของวิธีแก้ปัญหาของเรา:

#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