寻找两个正序数组的中位数 - 困难 - 算法题 - 算法 - 计算机

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2 。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

示例 2：

提示：

解法一：遍历查找（时间复杂度 O (m+n)）

思路：将两个数组合并起来，从小到大找到中间的那个数即可，当然也不需要合并两个数组，只需要将两个数组都从头开始找，相互比较，直到遍历到（m + n）/2 那里。需要注意的是合并的总数为偶数时，需要取中间两位数进行计算。还需要注意两个数组的临界点位置。

	class Solution {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
	// 两个数组的长度
	int length1 = nums1.length;
	int length2 = nums2.length;

	// 记录中间值
	int left = -1 ,right = -1;
	// 两个数组的下标位置
	int index1 = 0,index2 = 0;
	// 只需遍历到中位数的位置即可
	for (int i = 0; i <= (length1 + length2) / 2; i++){
	// 记录前一个的值（用于总长度为偶数时进行计算）
	left = right;

	// 当前数组 1 中的值小于当前数组 2 中的值时，将数组 1 的下标位置右移
	if (index1 < length1 && (index2 >= length2 \|\| nums1[index1] <= nums2[index2])){
	right = nums1[index1++];
	continue;
	}

	// 否则将数组 2 的下标位置右移
	right = nums2[index2++];
	}

	// 如果是偶数，则计算前一个值和当前值
	if ((length1 + length2) % 2 == 0){
	return (left + right) / 2.0;
	}

	// 如果是奇数，返回当前值
	return right;
	}
	}

想要达到 O (log (m+n)) 时间复杂度，得采用二分查找，详情查看力扣题解。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/