今天就不多廢話了我們直接上題目吧(難度:hard)
這次要講的是第四題:Median of Two Sorted Arrays

題目

翻譯

有兩個已經排序好的陣列num1和num2，且大小分別是m和n。
請找出這兩個陣列合併後的中位數，時間複雜度應為O(log(m+n))。
你可以假設陣列不會是空的。

解題步驟

以下是使用 Markdown 語法書寫的解題步驟：

解題步驟：

1. 問題分解
   根據總數的長度，決定中位數位置，並將問題轉化為「找到兩個數組的第 k 小數」。

2. 特殊情況處理
   當其中一個數組為空時，直接返回另一個數組中第 k 小的數。

3. 比較與捨棄
   遞迴選擇數組中的前半部分進行比較，並捨棄不可能包含第 k 小元素的部分。

4. 更新 k 值並重複步驟
   根據選擇捨棄的數量更新 k 的值，繼續遞迴。

5. 最終解答
   找到兩個數組的中位數並返回。

code

class Solution {
public:
    // Get the k-th element in two sorted arrays
    int getKth(const std::vector<int>& arr_s, const std::vector<int>& arr_l, int k) {
        int size_s = arr_s.size();
        int size_l = arr_l.size();
        
        if (size_s > size_l) {
            return getKth(arr_l, arr_s, k);
        }
        if (size_s == 0) {
            return arr_l[k - 1];
        }
        if (k == 1) {
            return std::min(arr_s[0], arr_l[0]);
        }

        int i = std::min(size_s, k / 2);
        int j = std::min(size_l, k / 2);

        if (arr_s[i - 1] > arr_l[j - 1]) {
            return getKth(arr_s, std::vector<int>(arr_l.begin() + j, arr_l.end()), k - j);
        } else {
            return getKth(std::vector<int>(arr_s.begin() + i, arr_s.end()), arr_l, k - i);
        }
    }

    // Find the median of two sorted arrays
    double findMedianSortedArrays(const std::vector<int>& nums1, const std::vector<int>& nums2) {
        int total_size = nums1.size() + nums2.size();
        int l = (total_size + 1) / 2;
        int r = (total_size + 2) / 2;

        return (getKth(nums1, nums2, l) + getKth(nums1, nums2, r)) / 2.0;
    }
};