在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