Số lượng số nguyên duy nhất tối đa trong Mảng con có kích thước nhất định trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng có kích thước n và một số M. Nhiệm vụ của chúng ta là tạo một chương trình sẽ tìm số lượng lớn nhất các số nguyên duy nhất trong Sub- mảng có kích thước đã cho.

Ở đây, chúng ta sẽ phải tìm mảng con kích thước M có số phần tử duy nhất tối đa.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng ={4, 1, 2, 1, 4, 3}. M =4

Đầu ra - 4

Giải thích -

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

Để giải quyết vấn đề này, chúng ta chỉ cần tạo tất cả các mảng con có kích thước M và sau đó đếm số phần tử duy nhất trong mảng con. Và kiểm tra xem số phần tử duy nhất có lớn hơn tổng số phần tử duy nhất tối đa toàn cầu hay không và lưu trữ giá trị lớn nhất của cả hai. Nhưng giải pháp này không hiệu quả.

Một giải pháp tốt hơn sẽ là sử dụng kỹ thuật cửa sổ trượt. Trong đó chúng tôi tạo một cửa sổ có kích thước m và sau đó sử dụng bảng băm để lưu trữ các phần tử duy nhất cho cửa sổ hiện tại.

Chúng tôi sẽ tạo cửa sổ theo cách sau -

• Tạo một cửa sổ có kích thước M và lưu trữ các phần tử trong một bản đồ băm.

• Sau đó di chuyển đến cửa sổ cho phần tử ở vị trí (M + 1) và xóa phần tử cho cửa sổ trước đó.

Hãy xem giải pháp này từ ví dụ của chúng tôi để hiểu rõ hơn về giải pháp -

Mảng ={4, 1, 2, 1, 4, 3}

Kích thước cửa sổ, M =4.

Giải pháp này cho thấy cách cửa sổ và Bản đồ băm được hình thành và số lượng phần tử duy nhất được tính .

Ví dụ

Chương trình tìm số lượng lớn nhất các số nguyên duy nhất trong Mảng con có kích thước cho trước -

#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;
}

Đầu ra

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