在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，9，12，15，19

第四个元素是5。

解决方法：

找到第m个最小元素的简单解决方案是创建一个合并的数组，然后按升序对数组进行排序，这将使该数组的第m个最小元素的索引为(m-1)。返回此输出值。

一个更有效的解决方案是使用最小堆 数据结构。

为此，我们将创建一个min堆并插入所有数组中的元素。然后m次从堆中删除min元素元素，并将输出存储到数组中。然后将下一个元素插入堆。

打印第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个k排序数组中的最小值是 "<<findMSmallestElement(arr, m);

   return 0;
}

6th个k排序数组中的最小值是 7