C++を使用したn範囲で発生した最大整数

この問題では、N個の範囲が与えられます。私たちのタスクは、n個の範囲で発生する最大の整数です。 。

すべての範囲の開始値と終了値。最も発生する値を見つける必要があります。

問題を理解するために例を見てみましょう

入力

S1 = 1, E1 = 3
S2 = 2, E2 = 6
S3 = 3, E3 = 4

出力

2

ソリューションアプローチ

問題を解決するための簡単なアプローチは、ハッシュを使用することです。ハッシュテーブルを使用して、すべてのメンバーとその数をカウントします。すべての範囲をトラバースし、カウントをハッシュテーブルに格納してから、最大カウントを見つけます。

線形時間の問題を解決する別のアプローチは、範囲配列を使用することです。この配列では、範囲のすべての開始値のインデックスを1を加算して更新し、範囲のすべての終了値を1を減算して更新します。はプレフィックス合計を検索し、最大プレフィックス合計値を検索します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int findMaxOccrEle(int L[], int R[], int n){
   int occurenceConut[MAX];
   memset(occurenceConut, 0, sizeof occurenceConut);
   int maxi = -1;
   for (int i = 0; i < n; i++) {
      occurenceConut[L[i]] += 1;
      occurenceConut[R[i] + 1];
      if(R[i]>maxi){
         maxi=R[i];
      }
   }
   int prefSum = occurenceConut[0],maxEleIndex;
   for (int i = 1; i < maxi+1; i++) {
      occurenceConut[i] += occurenceConut[i - 1];
      if (prefSum < occurenceConut[i]) {
         prefSum = occurenceConut[i];
         maxEleIndex = i;
      }
   }
   return maxEleIndex;
}
int main(){
   int L[] = { 1, 2, 3 };
   int R[] = { 3, 6, 4 };
   int n = sizeof(L) / sizeof(L[0]);
   cout<<"The maximum occurred integer in the range is "<<findMaxOccrEle(L, R, n);
   return 0;
}

出力

The maximum occurred integer in the range is 3