数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学C++ 中间隔中的最频繁数字
假设我们有一组整数区间的列表，其中每个元素都有一个区间，例如 [start, end]。我们必须找出在这些区间中出现次数最多的数字。如果有多个，则返回最小的数字。
因此，如果输入类似于 [[2, 5],[4, 6],[7, 10],[8, 10]]，则输出将为 4
为解决这个问题，我们将按照以下步骤进行 −
定义一个映射 m
cnt := 0，val := 0
对于 x 中的每个值 it −
(将 m[it[0]] 增加 1)
将 m[it[1] + 1] 减少 1
last := 0
对于 m 中的每个键 it
last := last + it 的值
如果 last > cnt，则
cnt := last
val := it
返回 val
让我们看看以下实现以获得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>>& x) {
map <int, int> m;
int cnt = 0;
int val = 0;
for(auto& it : x){
m[it[0]]++;
m[it[1] + 1]--;
}
int last = 0;
for(auto& it : m){
last += it.second;
if(last > cnt){
cnt = last;
val = it.first;
}
}
return val;
}
};
main() {
Solution ob;
vector<vector<int>> v = {{2, 5},{4, 6},{7, 10},{8, 10}};
cout << ob.solve(v);
}输入 −
{{2, 5},{4, 6},{7, 10},{8, 10}}输出
4
更新于： 02-Sep-2020
468 次浏览
广告