数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚科学
法律科学使用 C++ 获取 n 个范围中的最大整数
在该问题中，我们给出了 N 个范围。我们的任务是n 个范围中出现的最大整数。
对于所有范围的起始和结束值。我们需要找出出现次数最多的值。
我们举个例子来理解该问题：
输入
S1 = 1, E1 = 3 S2 = 2, E2 = 6 S3 = 3, E3 = 4
输出
2
解决方法
解决该问题的简单方法是使用哈希，我们将使用哈希表来统计所有成员及其计数。我们将遍历所有范围并在哈希表中存储计数，然后我们将找到最大计数。
线性时间内解决问题的另一种方法是使用范围数组。在此数组中，我们将通过将 1 添加到所有范围的起始值并从其中减去 1 来更新所有范围的结束值。这将找到前缀和并找到最大前缀和值。
示例
展示我们解决方案工作原理的程序
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int findMaxOccrEle(int L[], int R[], int n){
int occurenceConut[MAX];
memset(occurenceConut, 0, sizeof occurenceConut);
int maxi = -1;
for (int i = 0; i < n; i++) {
occurenceConut[L[i]] += 1;
occurenceConut[R[i] + 1];
if(R[i]>maxi){
maxi=R[i];
}
}
int prefSum = occurenceConut[0],maxEleIndex;
for (int i = 1; i < maxi+1; i++) {
occurenceConut[i] += occurenceConut[i - 1];
if (prefSum < occurenceConut[i]) {
prefSum = occurenceConut[i];
maxEleIndex = i;
}
}
return maxEleIndex;
}
int main(){
int L[] = { 1, 2, 3 };
int R[] = { 3, 6, 4 };
int n = sizeof(L) / sizeof(L[0]);
cout<<"The maximum occurred integer in the range is "<<findMaxOccrEle(L, R, n);
return 0;
}输出
The maximum occurred integer in the range is 3
更新于：2022 年 2 月 14 日
396 次查看
广告