题目描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

样例

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }

    int find(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);

        if (k == 1) {
            if (nums1.size() == i) return nums2[j];
            else return min(nums1[i], nums2[j]);
        }
        if (nums1.size() == i) return nums2[j + k - 1];
        // si, sj 表示 开始的index
        int si = min(i + k / 2, (int)nums1.size()), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1]) 
            return find(nums1, i, nums2, sj, k - (sj - j));
        else 
            return find(nums1, si, nums2, j, k - (si - i));
    }
};

Go 代码

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    tot := len(nums1) + len(nums2)
    if tot % 2 == 0 {
        left := find(nums1, 0, nums2, 0, tot / 2);
        right := find(nums1, 0, nums2, 0, tot / 2 + 1)
        return float64(left + right) / 2.0
    } else {
        return float64(find(nums1, 0, nums2, 0, tot / 2 + 1))
    }
}

func find(nums1 []int, i int, nums2 []int, j int, k int) int{
    if len(nums1) - i > len(nums2) - j {
        return find(nums2, j, nums1, i, k)
    }

    if len(nums1) == i {
        return nums2[j + k - 1]
    }
    if (k == 1) {
        return min(nums1[i], nums2[j])
    }

    si, sj := min(i + k / 2, len(nums1)), j + k - k / 2
    if nums1[si - 1] > nums2[sj - 1] {
        return find(nums1, i, nums2, sj, k - (sj - j))
    } else {
        return find(nums1, si, nums2, j, k - (si - i))
    }
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}