資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告