Số thường xuyên nhất trong khoảng thời gian trong C ++

Giả sử chúng ta có một danh sách danh sách các khoảng nguyên trong đó mỗi phần tử có khoảng như [bắt đầu, kết thúc]. Chúng tôi phải tìm ra con số xuất hiện thường xuyên nhất trong các khoảng thời gian. Nếu có ràng buộc, thì trả về số nhỏ nhất.

Vì vậy, nếu đầu vào là [[2, 5], [4, 6], [7, 10], [8, 10]], thì đầu ra sẽ là 4

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• Xác định một bản đồ m

• cnt:=0, val:=0

• cho mỗi giá trị nó bằng x -

  • (tăng m [it [0]] lên 1)

  • giảm m [it [1] + 1] 1

• cuối cùng:=0

• cho mỗi khóa, nó bằng m

  • last:=last + giá trị của nó

  • nếu cuối cùng> cnt, thì:

    • cnt:=cuối cùng

    • val:=it

• trả lại giá trị

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào -

{{2, 5},{4, 6},{7, 10},{8, 10}}

Đầu ra

4