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

4番目の要素は5です。

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

m番目に小さい要素を見つける簡単な解決策は、マージされた配列を作成し、配列のm番目に小さい要素がインデックス（m-1）になる昇順で配列を並べ替えることです。この出力値を返します。

より効果的な解決策は、最小ヒープを使用することです。 データ構造。

このために、最小ヒープを作成し、すべての配列から要素を挿入します。次に、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