4. 寻找两个正序数组的中位数 - 力扣(LeetCode)
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
本题要求nums1和nums2合并后数组的中位数。
如果一个数组的长度n:
本题的难点主要在于如何将两个有序数组合并为一个新的有序数组。
解题思路很简单,只要定义两个指针 i, j 初始分别指向nums1和nums2的首元素,然后比较nums1[i] 和 nums2[j] 的大小,较小者元素加入到合并数组中,并且对应指针++,然后继续比较,直到某个指针越界。
假设 i 指针越界,那么 j 指针必然不会越界,即必然有一个数组会先遍历完所有元素,另一个数组无法遍历完所有元素,此时我们需要将另一个未遍历完的数组整体加入到合并数组尾部。这样就可以得到一个有序合并数组了。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;
int[] merge = new int[n];
int i = 0;
int j = 0;
int k = 0;
while(i < nums1.length && j < nums2.length) {
if(nums1[i] < nums2[j]) {
merge[k++] = nums1[i++];
} else {
merge[k++] = nums2[j++];
}
}
while (i < nums1.length) {
merge[k++] = nums1[i++];
}
while (j < nums2.length) {
merge[k++] = nums2[j++];
}
int mid = n / 2;
if(n % 2 == 0) {
return (merge[mid] + merge[mid - 1]) / 2.0f;
} else {
return merge[mid];
}
}
}
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
const n = nums1.length + nums2.length;
const merge = new Array(n);
let i = 0;
let j = 0;
let k = 0;
while(i < nums1.length && j < nums2.length) {
if(nums1[i] < nums2[j]) {
merge[k++] = nums1[i++];
} else {
merge[k++] = nums2[j++];
}
}
while(i < nums1.length) {
merge[k++] = nums1[i++];
}
while(j < nums2.length) {
merge[k++] = nums2[j++];
}
const mid = Math.floor(n / 2);
if(n % 2 == 0) {
return (merge[mid] + merge[mid-1]) / 2;
} else {
return merge[mid];
}
};
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
n = len(nums1) + len(nums2)
merge = [0] * n
i = 0
j = 0
k = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
merge[k] = nums1[i]
i += 1
else:
merge[k] = nums2[j]
j += 1
k += 1
while i < len(nums1):
merge[k] = nums1[i]
i += 1
k += 1
while j < len(nums2):
merge[k] = nums2[j]
j += 1
k += 1
mid = n // 2
if n % 2 == 0:
return (merge[mid] + merge[mid - 1]) / 2.0
else:
return merge[mid]