Trong bài toán này, chúng ta được cung cấp k mảng có kích thước khác nhau. Nhiệm vụ của chúng ta là tìm giá trị nhỏ nhất thứ m trong k mảng đã sắp xếp.
Mô tả sự cố: Ở đây, chúng ta cần tìm phần tử nhỏ nhất thứ m của mảng được hợp nhất của tất cả k mảng.
Hãy lấy một ví dụ để hiểu vấ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 đã sắp xếp hợp nhất:2, 3, 4, 5, 6, 7, 9, 12, 15, 19
Yếu tố thứ 4 là 5.
Cách tiếp cận giải pháp:
Một giải pháp đơn giản để tìm phần tử nhỏ nhất thứ m là bằng cách tạo một mảng hợp nhất và sau đó sắp xếp mảng theo thứ tự tăng dần sẽ có phần tử nhỏ nhất thứ m của mảng ở chỉ số (m-1). Trả lại giá trị đầu ra này.
Một giải pháp hiệu quả hơn sẽ là sử dụng min heap cấu trúc dữ liệu.
Đối với điều này, chúng tôi sẽ tạo một heap tối thiểu và chèn các phần tử từ tất cả các mảng. Và sau đó m lần loại bỏ phần tử phần tử min khỏi heap và lưu trữ đầu ra vào mảng. Sau đó, chèn phần tử tiếp theo vào heap.
In mục đã xóa thứ m.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
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