leetcode-004

题目

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0

Example 2:

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

The median is (2 + 3)/2 = 2.5

分析

这个题目的意思是给出两个已排好序的数组，要求我们给出包含两个数组中所有数的中位数。我首先想到的方法是利用两个循环变量i， j来同时遍历这两个数组 nums1、nums2 ，当 nums1[i] < nums2[j]时i++ ，否则 j++ ，并且选出小的那个数，直到总共遍历了(m + n) / 2 个元素，有点类似于合并两个有序链表的算法。此时就可以找到中位数了：

1. 如果总数是奇数，那么中位数就是最后一个选出来的数
2. 如果总数是偶数，那么中位数就是最后两个选出来的数的平均数

代码如下：

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (m == 0) return n % 2 == 0 ? (nums2[n/2 - 1] + nums2[n/2]) / 2.0 : nums2[n/2];
        else if (n == 0) return m % 2 == 0 ? (nums1[m/2 - 1] + nums1[m/2]) / 2.0 : nums1[m/2];
        int mid = (m + n) / 2;
        vector<int> sortedArr;
        for (int i = 0, j = 0; i + j <= mid; ) {
            if (i == m) sortedArr.push_back(nums2[j++]);
            else if (j == n) sortedArr.push_back(nums1[i++]);
            else if (nums1[i] <= nums2[j]) sortedArr.push_back(nums1[i++]);
            else sortedArr.push_back(nums2[j++]);
        }
        return (m + n) % 2 == 0 ? (sortedArr[mid - 1] + sortedArr[mid]) / 2.0 : sortedArr[mid];
    }
};

这种方法的时间复杂度是 O((m + n) / 2), 并不满足题目要求的O(log(m + n)) ,因此还是得找效率更高的方法。

解法

实际上看到有 log 的复杂度，我们就应该想到要使用分治法，但这题要怎么使用二分法来把两个有序数组合并起来并找到中位数呢？其实，我们并不需要非得这样做，从中位数的定义入手，我们可以知道，如果数组中的一个数在把数组分成长度相等的两部分，且一部分的数值总大于等于另一部分，那这个数就是中位数，即：

把数组nums1 分成两个部分：

nums1[0],nums1[1]...nums1[i - 1] | nums1[i], nums1[i + 1]...nums[m - 1]

左边部分数目为i，右边部分数目为m - i
且 max(left) <= min(right)
当i = m - i 时（nums1[i - 1] + nums1[i]) / 2就是中位数

同理，我们无需把两个数组合并起来排序再找中位数，只需要把它们分成两个长度相等的部分，并使max(left) <= min(right)就可以找到中位数了，即：

nums1[0]...nums1[i - 1] | nums1[i]...nums1[m - 1]
nums2[0]...nums2[j - 1] | nums2[j]...nums2[n - 1]

• 长度相等即: i + j = m - i + n - j ,当总长度为奇数时左边会比右边少一个

• max(left) <= min(right) 即: nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]。

那么现在我们的问题就变成了找到这样的 i和j来满足上面两个条件。

i 的范围是 [0, m] ，由第一个条件可以知道 j = (m + n) / 2 - i ,当 m <= n 时 j >= 0 ，否则为负数

现在我们就可以用二分法来解决这个问题了，伪代码如下：

1.imin = 0, imax = m
2.j = (m + n) / 2 - i
3.
	if nums1[i - 1] > nums2[j] imax = i - 1		//i较大，因此需要减小遍历i的范围
	else if nums2[j - 1] > nums1[i] imin = i + 1	//i较小，因此需要增大遍历i的范围
	else 	//找到了合适的i
		if (m + n) % 2 == 0 return (max(left) + min(right)) / 2.0
        else return min(right)

当然我们需要考虑临界问题：i = 0, i = m, j = 0, j = n时怎么办？访问nums1[i - 1],nums2[j],nums2[j - 1],nums1[i]是可能越界的。

实际上，由j = (m + n) / 2 - i ，0 < i < m， n >= m可知0 < j < n，因此我们只需要判断i的临界范围就可以了。

对于nums1[i - 1] > nums2[j],需加上i > imin的判断，防止读取到nums1[-1]和nums2[n]

对于nums2[j - 1] > nums1[i],需加上i < imax的判断，防止读取到nums2[-1]和nums1[m]

最终代码如下：

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
   double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
       int m = nums1.size();
       int n = nums2.size();
       if (m > n) {     //确保n>=m
            nums1.swap(nums2);
            int temp = m;
            m = n;
            n = temp;
       }
       int imin = 0, imax = m, mid = (m + n) / 2;
       while (imin <= imax) {
            int i = (imin + imax) / 2;
            int j = mid - i;
            if (i > imin && nums1[i - 1] > nums2[j]) imax = i - 1;
            else if (i < imax && nums2[j - 1] > nums1[i]) imin = i + 1;
            else {//找到了使max(left) < min(right)的i
                int minRight;
                if (i == m) minRight = nums2[j];
                else if (j == n) minRight = nums1[i];
                else minRight = min(nums1[i], nums2[j]);
                if ((m + n) % 2 != 0) return minRight;

                int maxLeft;
                if (i == 0) maxLeft = nums2[j - 1];
                else if (j == 0) maxLeft = nums1[i - 1];
                else maxLeft = max(nums1[i - 1], nums2[j - 1]);

                return (maxLeft + minRight) / 2.0;
            }
       }
   }
};