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 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始
广告