資料結構
網路
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 次瀏覽
廣告