C++에서 주어진 n 범위에서 k번째로 작은 요소 찾기

이 문제에서는 n개의 범위와 정수 k가 주어집니다. 우리의 임무는 주어진 n 범위에서 k번째로 작은 요소를 찾는 것입니다.

범위를 결합한 후 생성된 배열에서 k번째로 작은 요소를 찾아야 합니다.

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

입력: 범위 ={{2, 5}, {7, 9}, {12, 15}}, k =9

출력: 13

설명:

생성된 배열은 {2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15}입니다.

가장 작은 요소는 13입니다.

해결 방법:

이 문제에 대한 간단한 해결책은 모든 범위에서 배열을 생성하는 것이며 범위에서 생성되기 때문에 오름차순으로도 정렬됩니다. 따라서 배열의 k 값을 찾기만 하면 됩니다.

우리 솔루션의 작동을 설명하는 프로그램,

예

#include <iostream>
using namespace std;

int main(){
   
   int arr[][2] = {{2, 5}, {7, 9}, {12, 15}};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 9;

   int rangeArr[1000];
   int size = 0;
   for(int i = 0; i < n; i++)
      for(int j = arr[i][0]; j <= arr[i][1]; j++) {
         rangeArr[size] = j;  
         size++;
      }
   if(k < size)
      cout<<k<<"th smallest element of the ranged array is "<<rangeArr[k]<<endl;
   else
      cout<<"invalid Index";
   return 0;
}

출력

9th smallest element of the ranged array is 13