資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告