C++の間隔で最も頻繁な数

各要素に[start、end]のような間隔がある整数間隔のリストのリストがあるとします。間隔内で最も頻繁に発生する数を見つける必要があります。同点の場合は、最小の数を返します。

したがって、入力が[[2、5]、[4、6]、[7、10]、[8、10]]の場合、出力は4

これを解決するには、次の手順に従います-

• 1つのマップを定義するm

• cnt：=0、val：=0

• 値ごとにx−

  • （m [it [0]]を1増やします）

  • m [it [1]+1]を1減らします

• 最後：=0

• キーごとにm

  で

  • 最後：=最後+その値

  • 最後の>cntの場合、次のようになります：

    • cnt：=最後

    • val：=it

• 戻り値

理解を深めるために、次の実装を見てみましょう-

例

#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