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