Trong bài toán này, ta được cho k mảng khác nhau với kích thước khác nhau. Nhiệm vụ là tìm giá trị nhỏ thứ m trong k mảng đã sắp xếp.
Mô tả bài toán: Cần tìm phần tử nhỏ thứ m của mảng gộp từ tất cả k mảng.
Ví dụ để hiểu bài toán:
Đầu vào: m = 4
arr[][] = { {4 , 7},
{2, 5, 6},
{3, 9, 12, 15, 19}}
Đầu ra: 5
Giải thích:
Mảng gộp đã sắp xếp: 2, 3, 4, 5, 6, 7, 9, 12, 15, 19
Phần tử thứ 4 là 5.
Phương pháp giải:
Một giải pháp đơn giản là tạo mảng gộp, sắp xếp tăng dần, phần tử nhỏ thứ m sẽ ở chỉ số (m-1). Trả về giá trị này.
Giải pháp hiệu quả hơn sử dụng cấu trúc dữ liệu min heap.
Ta tạo min heap và chèn phần tử đầu tiên của tất cả các mảng. Sau đó lặp m lần: lấy phần tử nhỏ nhất khỏi heap, lưu kết quả, chèn phần tử tiếp theo từ mảng tương ứng vào heap. Phần tử được lấy ra ở lần thứ m chính là kết quả.
Chương trình minh họa
Ví dụ
#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; }
Đầu ra
6th smallest value in k sorted arrays is 7