中位数

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)).

解法 计数法

取元素总数 n, 然后计数到 n/2 位置
如果 n 为奇数则停在中位数, 如果 n 为偶数则停在偏后的元素
用 pre 存前一个元素

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, curr = -1;
        int p1 = 0, p2 = 0;
        for (int i = 0; i <= n / 2; i++) {
            pre = curr;
            if (p1 == l1)
                curr = nums2[p2++];
            else if (p2 == l2)
                curr = nums1[p1++];
            else if (nums1[p1] < nums2[p2])
                curr = nums1[p1++];
            else
                curr = nums2[p2++];
        }
        if (n % 2 == 0)
            return (pre + curr) / 2.0;
        else
            return curr;
    }
}

go

package main

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	l1, l2 := len(nums1), len(nums2)
	n := l1 + l2
	p1, p2 := 0, 0
	var pre, curr int
	for i := 0; i <= n/2; i++ { // 第一步idx=0
		pre = curr
		switch {
		case p1 == l1:
			curr = nums2[p2]
			p2++
		case p2 == l2:
			curr = nums1[p1]
			p1++
		case nums1[p1] < nums2[p2]:
			curr = nums1[p1]
			p1++
		default:
			curr = nums2[p2]
			p2++
		}
	}
	if n%2 == 0 {
		return float64(pre+curr) / 2
	} else {
		return float64(curr)
	}
}