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

🔴   🔖  数组 二分查找 分治  🔗 力扣 LeetCode

题目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

题目大意

给定两个大小为 m 和 n 的有序数组 nums1 和  nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为  O(log(m + n))。

你可以假设 nums1  和  nums2  不会同时为空。

解题思路

这一题最容易想到的办法是把两个数组合并，然后取出中位数。但是合并有序数组的操作时间复杂度是 O(m+n) ，不符合题意。

由于题目要求的时间复杂度为 O(log(m + n))，这表明我们需要使用 二分查找。

可以将问题转化为 在两个排序数组中寻找第 k 小的数，其中 k 是 (m + n) / 2 或 (m + n) / 2 + 1，使用二分法来解决。

• 给定两个排序数组 nums1 和 nums2，需要找到第 k 小的数。
• 使用二分法来缩小查找范围：
  • 取两个数组中第 k / 2 个数，比较这两个数的大小。
  • 较小的那个数组的前 k / 2 个数不可能包含第 k 小的数，所以可以将这些数排除，并在剩余的部分继续查找。

特殊情况处理：

• 如果某一个数组为空，则直接返回另一个数组的中间值。
• 如果 k == 1，则返回两个数组的最小值。
• 总长度为偶数时，需要同时找到第 (m + n) / 2 和第 (m + n) / 2 + 1 小的数，并取它们的平均值作为中位数。

复杂度分析

• 时间复杂度：O(log(min(m, n)))，因为每次递归我们会排除掉 k/2 个元素，直到找到第 k 小的元素，整个过程是对较短数组长度的二分查找。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
	const findKth = (arr1, start1, arr2, start2, k) => {
		// 如果数组 1 已经全部被排除，则返回数组 2 中的第 k 小元素
		if (start1 >= arr1.length) {
			return arr2[start2 + k - 1];
		}

		// 如果数组 2 已经全部被排除，则返回数组 1 中的第 k 小元素
		if (start2 >= arr2.length) {
			return arr1[start1 + k - 1];
		}

		// 如果 k == 1，返回两个数组中最小的元素
		if (k == 1) {
			return Math.min(arr1[start1], arr2[start2]);
		}

		// 在两个数组中分别找出第 k/2 个元素
		let harfK = (k / 2) | 0,
			index1 = start1 + harfK - 1,
			index2 = start2 + harfK - 1,
			mid1 = index1 < arr1.length ? arr1[index1] : Infinity,
			mid2 = index2 < arr2.length ? arr2[index2] : Infinity;

		// 如果数组 1 的中间值较小，排除数组 1 中的前 k/2 个元素
		if (mid1 < mid2) {
			return findKth(arr1, start1 + harfK, arr2, start2, k - harfK);
		} else {
			// 否则排除数组 2 中的前 k/2 个元素
			return findKth(arr1, start1, arr2, start2 + harfK, k - harfK);
		}
	};

	const len = nums1.length + nums2.length;
	// 如果总长度为奇数，返回中间的那个数
	if (len % 2 == 1) {
		return findKth(nums1, 0, nums2, 0, ((len / 2) | 0) + 1);
	} else {
		// 如果总长度为偶数，返回中间两个数的平均值
		const left = findKth(nums1, 0, nums2, 0, len / 2);
		const right = findKth(nums1, 0, nums2, 0, len / 2 + 1);
		return (left + right) / 2;
	}
};

相关题目

题号	标题	题解	标签	难度
2387	行排序矩阵的中位数 🔒		数组 二分查找 矩阵