数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在 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-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
更新于：2021年1月25日
167 次浏览
广告