ในปัญหานี้ เราได้รับ k อาร์เรย์ที่มีขนาดต่างกัน งานของเราคือ หาค่าที่น้อยที่สุดเป็นอันดับที่ m ในอาร์เรย์ที่เรียงลำดับ k
คำอธิบายปัญหา: ที่นี่ เราต้องหาองค์ประกอบที่เล็กที่สุดเป็นอันดับที่ m ของอาร์เรย์ที่ผสานของอาร์เรย์ k ทั้งหมด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: ม =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 ของอาร์เรย์ที่ดัชนี (m-1) ส่งคืนค่าเอาต์พุตนี้
วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการใช้ min heap โครงสร้างข้อมูล
สำหรับสิ่งนี้ เราจะสร้างฮีปขั้นต่ำและแทรกองค์ประกอบจากอาร์เรย์ทั้งหมด จากนั้น 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
