หาค่าที่ m-th น้อยที่สุดใน k อาร์เรย์ที่เรียงแล้วใน C++

โจทย์

ได้รับ k อาร์เรย์ที่เรียงแล้ว ขนาดต่างกัน ทางเราต้อง หาค่าที่ m-th น้อยที่สุดในอาร์เรย์ที่รวมกันทั้งหมด

ตัวอย่าง

Input: m = 4, arr[][] = {{4, 7}, {2, 5, 6}, {3, 9, 12, 15, 19}}

Output: 5

อธิบาย: อาร์เรย์รวมเรียงแล้ว: 2, 3, 4, 5, 6, 7, 9, 12, 15, 19 -> ตัวที่ 4 คือ 5

แนวทางแก้ปัญหา

วิธีแบบง่าย: รวมอาร์เรย์ทั้งหมด เรียง แล้วหาตัวที่ (m-1)

วิธีที่มีประสิทธิภาพ (Min Heap):

สร้าง Min Heap ใส่ตัวแรกของแต่ละอาร์เรย์ พร้อมกับดัชนีอาร์เรย์และดัชนีในอาร์เรย์
ทำซ้ำ m รอบ: ดึงค่าน้อยที่สุดออกจาก Heap แล้วใส่ตัวถัดไปจากอาร์เรย์เดิมเข้า Heap
ค่าที่ดึงออกมาในรอบที่ 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, i = 0, j = 0;
    while (count < m && !priorQueue.empty()) {
        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