จำนวนสูงสุดของจำนวนเต็มเฉพาะในอาร์เรย์ย่อยของขนาดที่กำหนดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ขนาด n และตัวเลข M หน้าที่ของเราคือสร้างโปรแกรมที่จะ ค้นหาจำนวนเต็มสูงสุดที่ไม่ซ้ำใน Sub- อาร์เรย์ของขนาดที่กำหนด

ในที่นี้ เราจะต้องหาอาร์เรย์ย่อยของ size M ที่มีจำนวนองค์ประกอบที่ไม่ซ้ำกันสูงสุด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − อาร์เรย์ ={4, 1, 2, 1 , 4, 3} M =4

ผลผลิต − 4

คำอธิบาย −

All possible combinations of sub-arrays of size 4.
{4, 1, 2, 1} = 3 unique elements
{1, 2, 1, 4} = 3 unique elements
{2, 1, 4, 3} = 4 unique elements

ในการแก้ปัญหานี้ เราจะสร้างอาร์เรย์ย่อยทั้งหมดที่มีขนาด M แล้วนับจำนวนองค์ประกอบที่ไม่ซ้ำในอาร์เรย์ย่อย และตรวจสอบว่าจำนวนองค์ประกอบที่ไม่ซ้ำมากกว่าจำนวนองค์ประกอบที่ไม่ซ้ำสูงสุดทั่วโลกหรือไม่ และเก็บค่าสูงสุดของทั้งสองไว้ แต่วิธีนี้ไม่ได้ผล

ทางออกที่ดีกว่าคือการใช้เทคนิคหน้าต่างบานเลื่อน โดยที่เราสร้างหน้าต่างขนาด m แล้วใช้ตารางแฮชเพื่อจัดเก็บองค์ประกอบเฉพาะสำหรับหน้าต่างปัจจุบัน

เราจะสร้างหน้าต่างด้วยวิธีต่อไปนี้ -

• สร้างหน้าต่างขนาด M และจัดเก็บองค์ประกอบในแมปแฮช

• จากนั้นย้ายไปยังหน้าต่างสำหรับองค์ประกอบที่ตำแหน่ง (M+1) และนำองค์ประกอบสำหรับหน้าต่างก่อนหน้าออก

มาดูวิธีแก้ปัญหานี้จากตัวอย่างของเราเพื่อทำความเข้าใจวิธีแก้ปัญหาให้ดีขึ้น -

อาร์เรย์ ={4, 1, 2, 1, 4, 3}

ขนาดหน้าต่าง M =4.

โซลูชันนี้แสดง วิธีการสร้างหน้าต่างและแฮชแมปและการนับจำนวนองค์ประกอบที่ไม่ซ้ำ .

ตัวอย่าง

โปรแกรมค้นหาจำนวนสูงสุดของจำนวนเต็มที่ไม่ซ้ำกันในอาร์เรย์ย่อยของขนาดที่กำหนด -

#include<bits/stdc++.h>
using namespace std;
int maxUniqueElement(int a[],int N,int M){
   map<int,int> hashMap;
   int uniqueCountWindow=0;
   int uniqueCount=0;
   for(int i=0;i<M;i++) {
      if(hashMap.find(a[i])==hashMap.end()) {
         hashMap.insert(make_pair(a[i],1));
         uniqueCountWindow++;
      }
      else
         hashMap[a[i]]++;
      }
      uniqueCount = uniqueCountWindow;
      for(int i=M;i<N;i++) {
         if(hashMap[a[i-M]]==1) {
            hashMap.erase(a[i-M]);
            uniqueCountWindow--;
         }
         else
            hashMap[a[i-M]]--;
            if(hashMap.find(a[i])==hashMap.end()){
               hashMap.insert(make_pair(a[i],1));
               uniqueCountWindow++;
            }
            else
               hashMap[a[i]]++;
               uniqueCount=max(uniqueCount,uniqueCountWindow);
         }
      return uniqueCount;
}
int main(){
   int arr[] = {4, 1 ,2, 1, 4, 3};
   int M=4;
   int N=sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum number of unique elements in sub-array of size "<<M<<" is "<<maxUniqueElement(arr,N,M)<<endl;
}

ผลลัพธ์

The maximum number of unique elements in sub-array of size 4 is 4