题解 | #NC413 两个升序数组的中位数#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums1 int整型vector 
     * @param nums2 int整型vector 
     * @return double浮点型
     */
    double Median(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int mid1 = (m + n + 1) / 2;
        int mid2 = (m + n + 2) / 2;
        return (getKthElement(nums1, 0, nums2, 0, mid1) + getKthElement(nums1, 0, nums2, 0, mid2)) / 2.0;
     }
     //在两个有序数组中找到第k个元素（例如找第一个元素，k=1，即nums[0]）
    //i: nums1的起始位置 j: nums2的起始位置（i，j都是从0开始）
    int getKthElement(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        //若nums1为空（或是说其中数字全被淘汰了）
        //在nums2中找第k个元素，此时nums2起始位置是j，所以是j+k-1
        if (i >= nums1.size()) return nums2[j + k - 1];
        if (j >= nums2.size()) return nums1[i + k - 1];
        
        //递归出口
        //当K=1时候，相当于求最小值，我们只要比较nums1和nums2的起始位置i和j上的数字就可以了。
        if (k == 1) return min(nums1[i], nums2[j]);
        //这两个数组的第K/2小的数字，若不足k/2个数字则赋值整型最大值，以便淘汰另一数组的前k/2个数字
        int mid1 = i + k / 2 - 1 < nums1.size() ? nums1[i + k / 2 - 1] : INT_MAX;
        int mid2 = j + k / 2 - 1 < nums2.size() ? nums2[j + k / 2 - 1] : INT_MAX;
        
        //二分
        if (mid1 < mid2) {
            return getKthElement(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return getKthElement(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }
};