หา Median ในเมทริกซ์ที่เรียงลำดับตามแถวใน C++

คำอธิบายปัญหา

ได้รับเมทริกซ์ 2D ขนาด r x c ที่ เรียงลำดับตามแถว (Row-wise Sorted) ต้องการหา Median (ค่ามัธยฐาน) ของสมาชิกทั้งหมดในเมทริกซ์

ตัวอย่าง

Input: mat = { {2, 4, 7}, {5, 6, 8}, {4, 8, 9} }

Output: 6

คำอธิบาย: รวมสมาชิกทั้งหมด → {2, 4, 4, 5, 6, 7, 8, 8, 9} → Median คือ 6 (ค่ากึ่งกลางของ 9 ค่า)

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

วิธีที่ 1: Brute Force (ง่ายแต่ช้า)

นำสมาชิกทั้งหมดใส่อาร์เรย์ เรียงลำดับ แล้วหาค่ากึ่งกลาง → Time: O(rc log rc), Space: O(rc)

วิธีที่ 2: Binary Search บนช่วงค่า (มีประสิทธิภาพ)

ใช้ข้อเท็จจริง: Median คือค่าที่มีสมาชิกน้อยกว่ามันอยู่พอดี (r*c)/2 ตัว

1. หา smallest (ค่าน้อยสุดในเมทริกซ์) และ largest (ค่ามากสุด)
2. Binary Search ระหว่าง smallest ถึง largest:
   • หา mid = ค่ากึ่งกลางช่วง
   • นับจำนวนสมาชิกที่ น้อยกว่า mid ในแต่ละแถว (ใช้ upper_bound เพราะแถวเรียงแล้ว)
   • ถ้าจำนวนน้อยกว่า (r*c+1)/2 → ย้าย smallest = mid + 1
   • มิฉะนั้น → ย้าย largest = mid
3. เมื่อ smallest == largest → ได้ Median

Time Complexity: O(r log c log(max-min)), Space: O(1)

โค้ดตัวอย่าง C++

#include <bits/stdc++.h>
using namespace std;

#define c 3
#define r 3

int findMedian(int mat[][c]) {
    int smallest = INT_MAX, largest = INT_MIN;
    
    // หาค่าน้อยสุดและมากสุด
    for (int i = 0; i < r; i++) {
        if (mat[i][0] < smallest) smallest = mat[i][0];
        if (mat[i][c-1] > largest) largest = mat[i][c-1];
    }
    
    while (smallest < largest) {
        int mid = smallest + (largest - smallest) / 2;
        int smallCount = 0;
        
        // นับจำนวนสมาชิก < mid ในแต่ละแถว
        for (int i = 0; i < r; ++i)
            smallCount += upper_bound(mat[i], mat[i] + c, mid) - mat[i];
        
        if (smallCount < ((r * c + 1) / 2))
            smallest = mid + 1;
        else
            largest = mid;
    }
    return smallest;
}

int main() {
    int mat[][c] = { {2, 5, 7}, {4, 6, 8}, {1, 8, 9} };
    cout << "The median of the matrix is " << findMedian(mat);
    return 0;
}

ผลลัพธ์

The median of the matrix is 6