中位数
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)
}
}