数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告