Skip to content

中位数

2 个序列的中位数

4. 寻找两个正序数组的中位数 hard

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

算法的时间复杂度应该为 O(log (m+n))
The overall run time complexity should be O(log (m+n)).

解法 1 计数法

取元素总数 n, 然后从第 0 个开始计数, 直到 n/2
如果 n 为奇数则停在中位数, 如果 n 为偶数则停在偏后的元素

java
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        int n = l1 + l2;
        int pre = -1, num = -1;
        int p1 = 0, p2 = 0;
        for (int i = 0; i <= n / 2; i++) {
            pre = num;
            if (p1 == l1)
                num = nums2[p2++];
            else if (p2 == l2)
                num = nums1[p1++];
            else if (nums1[p1] < nums2[p2])
                num = nums1[p1++];
            else
                num = nums2[p2++];
        }
        if (n % 2 == 0)
            return (pre + num) / 2.0;
        else
            return num;
    }
}
go
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    l1, l2 := len(nums1), len(nums2)
    n := l1 + l2
    p1, p2 := 0, 0
    var pre, num int
    for i := 0; i <= n/2; i++ { // 第一步idx=0
        pre = num
        if p1 == l1 {
            num = nums2[p2]
            p2++
        } else if p2 == l2 {
            num = nums1[p1]
            p1++
        } else if nums1[p1] < nums2[p2] {
            num = nums1[p1]
            p1++
        } else {
            num = nums2[p2]
            p2++
        }
    }
    if n%2 == 0 {
        return float64(pre+num) / 2
    } else {
        return float64(num)
    }
}