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 次瀏覽

開啟你的 職業生涯

完成課程即可獲得認證

開始
廣告