数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找元素数量最大子集，使得这些元素的绝对差小于或等于 1
假设我们有一个包含 n 个元素的数组。我们必须找到从数组中选择元素的最大数量，使得所选元素中的任意两个元素之间的绝对差小于或等于 1。因此，如果数组类似于 [2, 2, 3, 4, 5]，则元素将为 3，因此具有最大计数的序列为 2, 2, 3。
0 和 1 的绝对差意味着数字可以是 x 和 x + 1 类型。所以思路是存储数组元素的频率。因此，如果我们找到任意两个连续元素的最大和，它将是解决方案。
示例
#include <iostream>
#include <map>
using namespace std;
int maxElem(int arr[], int n) {
map<int,int> occurrence;
for(int i=0;i<n;++i){
if(occurrence[arr[i]])
occurrence[arr[i]] += 1;
else
occurrence[arr[i]] = 1;
}
int ans = 0, key;
map<int,int>:: iterator it=occurrence.begin();
while(it!=occurrence.end()) {
key = it->first;
++it;
if(occurrence[key+1]!=0)
ans=max(ans,occurrence[key]+occurrence[key+1]);
}
return ans;
}
int main(){
int arr[] = {2, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Result is: " << maxElem(arr, n);
}输出
Result is: 3
更新于: 2019-12-18
267 次浏览
广告