LeetCode Solution: 4. Median of Two Sorted Arrays

描述

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

Follow up: 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.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

Constraints:

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

解析

解析1：暴力解法。

因为知道两个数组的长度

1. 如果两数组长度之和为偶数，则中位数为第(m+n+1)/2与(m+n+2)/2之和的二分之一
2. 如果两数组长度之和为奇数，则中位数为第(m+n+1)/2个数

循环遍历两个数组，抛弃掉小的那一个数，前进直到找到想要的数。

时间复杂度O(n)

解析2：利用二分法思想

class Solution {
public:
	double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2)
	{
		int m = nums1.size();
		int n = nums2.size();
		int left = (m+n+1)/2;
		int right = (m+n+2)/2;
		bool odd = (m + n) / 2 != 0;

		if(odd)
			return (findKth(nums1, 0, nums2, 0, right)
						+ findKth(nums1, 0, nums2, 0, left)) / 2.0;
		else
			return findKth(nums1, 0, nums2, 0, left);
	}

	static int findKth(std::vector<int> &nums1, int i, std::vector<int> &nums2, int j, int k)
	{
		//the goal is to find the kth number in nums1 and nums2
		if (i >= nums1.size())
			//if i > nums1.size() return kth number in nums2;
			return nums2[j+k-1];
		if (j >= nums2.size())
			return nums1[i+k-1];
		if (k == 1)
			return std::min(nums1[i], nums2[j]);

		int midVal1 = (i + k/2 -1) < nums1.size() ? nums1[i+k/2-1] : INT_MAX;
		int midVal2 = (j + k/2 -1) < nums2.size() ? nums2[j+k/2-1] : INT_MAX;

		if (midVal1 < midVal2)
			//weed out index i to k/2 of num1s
			return findKth(nums1, i+k/2, nums2, j, k-k/2);
		else
			return findKth(nums1, i, nums2, j+k/2, k-k/2);
	}
};

利用二分法的思想可以将时间复杂度降到O(log(m+n))

double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2)
{
	int m = nums1.size();
	int n = nums2.size();
	int left = (m+n+1)/2;
	int right = (m+n+2)/2;
	bool odd = (m + n) / 2 != 0;

	if(odd)
		return (findKth(nums1, 0, nums2, 0, right)
					+ findKth(nums1, 0, nums2, 0, left)) / 2.0;
	else
		return findKth(nums1, 0, nums2, 0, left);
}

首先来看第一个函数，

• m代表nums1的大小
• n代表nums2的大小
• left表示中间两个元素的左边那个
• right表示中间元素的右边那个（如果为数组和大小为奇数时，left和right是相等的）
• odd用来判断数组大小之和是否为奇数

最后判断一下，如果是奇数的话，只需要调用一次函数，避免函数调用的开销。

关键点在第二个函数上

int findKth(std::vector<int> &nums1, int i, std::vector<int> &nums2, int j, int k)

• i表示，数组一从index i开始
• j表示，数组二从index j开始
• k表示，要寻找的元素在第k位（从1开始算的第k位，不是index k)

static int findKth(std::vector<int> &nums1, int i, std::vector<int> &nums2, int j, int k)
	{
		//the goal is to find the kth number in nums1 and nums2
		if (i >= nums1.size())
			return nums2[j+k-1];
		if (j >= nums2.size())
			return nums1[i+k-1];
		if (k == 1)
			return std::min(nums1[i], nums2[j]);

		int midVal1 = (i + k/2 -1) < nums1.size() ? nums1[i+k/2-1] : INT_MAX;
		int midVal2 = (j + k/2 -1) < nums2.size() ? nums2[j+k/2-1] : INT_MAX;

		if (midVal1 < midVal2)
			//weed out index i to k/2 of num1s
			return findKth(nums1, i+k/2, nums2, j, k-k/2);
		else
			return findKth(nums1, i, nums2, j+k/2, k-k/2);
	}
};

这个函数就是去想要一个概念数组，里面的元素是排好序的nums1和nums2，目的是为了淘汰第k位之前的元素以找到nums[k]

退出条件

1. 如果i（j同理）（数组的起始位置）都比数组的大小还大了，那么说明要找的元素一定不在nums1里面，则把nums1的所有元素淘汰掉，直接返回nums2从j开始的第k位元素。

2. 如果k==1的时候，表示从第i开始的第一个，只剩一个可以选择了，当然是选择两个之中小的一个 。

令midVal1为数组1中间那个数，midVal2为数组2中间那个数，那么每次可以淘汰掉前k/2个，例如midVal2比midVal1小的时候，数组2以j开始的后k/2个数据只能作为我们要找的概念数组的第k个数据的垫脚石

当淘汰掉k/2后，需要找的元素就是index往后k/2后的第k/2个！

直到满足两个退出条件之一后退出即可

时间复杂度为O(log(m+n))

总结

这是一道很经典的题，思路也很新奇，在秋招的时候几个大厂出了这样的题，前几天面腾讯的时候面试官也问了。

记下来!