資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中給定大小的子陣列中唯一整數的最大數量
在這個問題中，我們給定一個大小為 n 的陣列和一個數字 M。我們的任務是建立一個程式來查詢給定大小的子陣列中唯一整數的最大數量。
在這裡，我們將必須找到具有最大唯一元素數的 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。
| 視窗 | 雜湊對映 | 唯一元素的數量 | 新增的元素 | 刪除的元素 |
| {4,1,2,1} | 4,1,2 | 3 | - | - |
| {1,2,1,4} | 1,2,4 | 3 | 4 | 4 |
| {2,1,4,3} | 2,1,4,3 | 4 | 3 | 1 |
此解決方案顯示了視窗和雜湊對映是如何形成的以及唯一元素的數量是如何計算的。
示例
查詢給定大小的子陣列中唯一整數的最大數量的程式 -
#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
更新於: 2020年6月3日
234 次檢視
廣告