C++에서 k 정렬된 배열에서 m번째 가장 작은 값 찾기

이 문제에서는 크기가 다른 k개의 서로 다른 배열이 제공됩니다. 우리의 임무는 k개의 정렬된 배열에서 m번째로 작은 값을 찾는 것입니다.

문제 설명: 여기에서 우리는 모든 k 배열의 병합된 배열의 m번째 가장 작은 요소를 찾아야 합니다.

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

입력: m =4

arr[][] ={ {4, 7},
{2, 5, 6},
{3, 9, 12, 15, 19}}

출력: 5

설명:

병합 정렬된 배열 :2, 3, 4, 5, 6, 7, 9, 12, 15, 19

네 번째 요소는 5입니다.

해결 방법:

m번째로 작은 요소를 찾는 간단한 솔루션은 병합된 배열을 만든 다음 인덱스(m-1)에서 배열의 m번째로 작은 요소가 있는 오름차순으로 배열을 정렬하는 것입니다. 이 출력 값을 반환합니다.

보다 효과적인 솔루션은 최소 힙 을 사용하는 것입니다. 데이터 구조.

이를 위해 최소 힙을 만들고 모든 배열에서 요소를 삽입합니다. 그런 다음 m 번 힙에서 최소 요소 요소를 제거하고 출력을 배열에 저장합니다. 그런 다음 힙에 다음 요소를 삽입합니다.

m번째 제거된 항목을 인쇄합니다.

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

예시

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, pair<int, int> > ppi;

int findMSmallestElement(vector<vector<int> > sortedArr, int m) {
   
   priority_queue<ppi, vector<ppi>, greater<ppi> > priorQueue;

   for (int i = 0; i < sortedArr.size(); i++)
      priorQueue.push({ sortedArr[i][0], { i, 0 } });
   int count = 0;
   int i = 0, j = 0;
   while (count < m && priorQueue.empty() == false) {
      ppi curr = priorQueue.top();
      priorQueue.pop();
      i = curr.second.first;
      j = curr.second.second;
      if (j + 1 < sortedArr[i].size())
         priorQueue.push( { sortedArr[i][j + 1], { i, (j + 1) } });
      count++;
   }
   return sortedArr[i][j];
}

int main() {
   
   vector<vector<int> > arr{ {4 , 7},
                         {2, 5, 6},
                         {3, 9, 12, 15, 19}};
   int m = 6;
   cout<<m<<"th smallest value in k sorted arrays is "<<findMSmallestElement(arr, m);

   return 0;
}

출력

6th smallest value in k sorted arrays is 7