C++에서 주어진 N 범위에 의해 생성된 시리즈에서 k번째 요소 찾기

이 문제에서는 행렬 범위[N][2]와 정수 값 k로 간격 L - R 사이의 N 범위의 정수 값이 제공됩니다. 우리의 임무는 주어진 N 범위에 의해 생성된 시리즈에서 k번째 요소를 찾는 것입니다. .

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : ranges[][] = {{1, 3}, {5, 7}}, k = 4
Output : 5

설명 -

The series is {1, 2, 3, 5, 6, 7}
The 4th element is 5.

해결 방법

문제에 대한 간단한 해결책은 주어진 범위에 대해 일련의 정수를 생성한 다음 해당 배열의 인덱스 k에서 요소를 찾는 것입니다.

예

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
   int rangeVal[10000];
   int rangeSize = 0;
   for(int i = 0; i < n; i++){
      for(int j = range[i][0]; j <= range[i][1]; j++){
         rangeVal[rangeSize] = j;
         rangeSize++;
      }
   }
   return rangeVal[k-1];
}
int main(){
   int L[] = { 1, 5 };
   int R[] = { 3, 8 };
   int range[][2] = {{1, 3}, {5, 8}};
   int n = sizeof(L) / sizeof(int);
   int k = 4;
   cout<<k<<"-th element of the series generated by ranges is "<<
   findKthSmallestEleSeries(n, k, range); 
   return 0;
}

출력

4-th element of the series generated by ranges is 5

이 방법은 좋지만 범위가 너무 크면 메모리 문제가 발생할 수 있습니다. 따라서 배열의 모든 요소를 ​​저장하는 더 나은 접근 방식을 도출해야 합니다.

또 다른 접근 방식

문제를 해결하는 또 다른 방법은 이진 검색과 카운터 배열을 사용하는 것입니다. 카운터 배열은 주어진 범위까지 정수의 개수를 저장합니다. count[i] =i번째 범위까지의 문자 개수입니다.

그런 다음 k에 대해 k번째로 작은 값이 있는 범위 번호 i를 찾습니다.

그런 다음 이 범위에서 값을 찾습니다.

예

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
   int start = 1;
   int end = n;
   int count[n + 1];
   count[0] = 0;
   for (int i = 0; i < n; i++)
      count[i + 1] = count[i] + (range[i][1] - range[i][0]) + 1;
   int index = -1;
   int mid;
   while (start <= end) {
      mid = (start + end) / 2;
      if (count[mid] > k) {
         index = mid;
         end = mid - 1;
      }
      else if (count[mid] < k) 
         start = mid + 1;
      else {
         index = mid;
         break;
      }
   }
   start = range[index - 1][0];
   end = range[index - 1][1];
   int indexK = k - count[index - 1];
   while (start <= end) {
      mid = (start + end) / 2;
      if ((mid - range[index - 1][0]) + 1 == indexK) {
         return mid;
      }
      else if ((mid - range[index - 1][0]) + 1 > indexK)
         end = mid - 1;
      else
         start = mid + 1;
   }
   return -1;
}
int main(){
   int L[] = { 1, 5 };
   int R[] = { 3, 8 };
   int range[][2] = {{1, 3}, {5, 8}};
   int n = sizeof(L) / sizeof(int);
   int k = 4;
   cout<<k<<"-th element of the series generated by ranges is "<<
   findKthSmallestEleSeries(n, k, range);
   return 0;
}

출력

4-th element of the series generated by ranges is 5