โปรแกรมหา Median ของอาร์เรย์ที่เรียงลำดับแล้ว 2 อาร์เรย์ใน C++

เราได้รับอาร์เรย์ที่เรียงลำดับแล้ว 2 อาร์เรย์ เป้าหมายคือหา median ของข้อมูลรวมทั้งสองอาร์เรย์

ตัวอย่าง: [1,5,8] และ [2,3,6,9] → Median = 5

แนวทางการแก้ปัญหา (Binary Search O(log(min(m,n))))

ใช้ binary search บนอาร์เรย์ที่สั้นกว่า หา partition ที่ทำให้:

• maxLeftX ≤ minRightY
• maxLeftY ≤ minRightX

เมื่อเจา partition ที่ถูกต้อง:

• ถ้าจำนวนรวมเป็นคู่: median = (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
• ถ้าจำนวนรวมเป็นคี่: median = max(maxLeftX, maxLeftY)

การนำไปใช้ (Implementation)

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

class Solution {
public:
    double solve(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return solve(nums2, nums1);
        
        int x = nums1.size();
        int y = nums2.size();
        int low = 0, high = x;
        int totalLength = x + y;
        
        while (low <= high) {
            int partitionX = low + (high - low) / 2;
            int partitionY = (totalLength + 1) / 2 - partitionX;
            
            int maxLeftX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
            int minRightX = (partitionX == x) ? INT_MAX : nums1[partitionX];
            int maxLeftY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
            int minRightY = (partitionY == y) ? INT_MAX : nums2[partitionY];
            
            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if (totalLength % 2 == 0) {
                    return ((double)max(maxLeftX, maxLeftY) + (double)min(minRightX, minRightY)) / 2;
                } else {
                    return max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }
        return 0;
    }
};

int main() {
    Solution ob;
    vector<int> v1 = {1, 5, 8}, v2 = {2, 3, 6, 9};
    cout << ob.solve(v1, v2);
    return 0;
}

อินพุต

[1,5,8], [2,3,6,9]

เอาต์พุต

5