Median of Two Sorted Arrays ใน C++

สมมติว่าเรามีอาร์เรย์สองตัว ซึ่งถูกเรียงลำดับแล้ว เราต้องหา median ของอาร์เรย์ทั้งสองนี้ เช่นถ้าอาร์เรย์คือ [1,5,8] และ [2,3,6,9] คำตอบจะเป็น 5

ขั้นตอนการแก้ปัญหา

กำหนดฟังก์ชัน findMedianSortedArrays รับ nums1 และ nums2
ถ้าขนาดของ nums1 > ขนาดของ nums2 เรียกฟังก์ชันซ้ำด้วยลำดับสลับ
x := ขนาดของ nums1, y := ขนาดของ nums2
low := 0, high := x
totalLength := x + y
while low <= high
- partitionX := low + (high - low) / 2
- partitionY := (totalLength + 1) / 2 - partitionX
- maxLeftX = -inf ถ้า partitionX เป็น 0 มิฉะนั้น nums1[partitionX-1]
- minRightX = inf ถ้า partitionX เป็น x มิฉะนั้น nums1[partitionX]
- maxLeftY = -inf ถ้า partitionY เป็น 0 มิฉะนั้น nums2[partitionY-1]
- minRightY = inf ถ้า partitionY เป็น y มิฉะนั้น nums2[partitionY]
- ถ้า maxLeftX <= minRightY และ maxLeftY <= minRightX
  - ถ้า totalLength mod 2 เท่ากับ 0
    - คืนค่า (max ของ maxLeftX และ maxLeftY + min ของ minRightX และ minRightY) / 2
  - มิฉะนั้น
    - คืนค่า max ของ maxLeftX และ maxLeftY
- มิฉะนั้นถ้า maxLeftX > minRightY
  - high := partitionX - 1
- มิฉะนั้น low := partitionX + 1
คืนค่า 0

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

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

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size())
            return findMedianSortedArrays(nums2, nums1);
        int x = nums1.size();
        int y = nums2.size();
        int low = 0;
        int 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.findMedianSortedArrays(v1, v2));
}

อินพุต

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

Median of Two Sorted Arrays ใน C++

ขั้นตอนการแก้ปัญหา

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

อินพุต

เอาต์พุต