[LeetCode]4. Median of Two Sorted Arrays

发表于 | 更新于: | 分类于 | | 阅读次数:

Problem

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: 

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

The median is 2.0

Example 2: 

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

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

Solution

解析

题目给出两个有序数组，大小分别为m和n，计算两个有序数组的中位数。时间复杂度要求O( log(m+n) ).同时假设数组1和数组2不可能同时为空。

最原始的想法是使用归并排序的merge函数，生成一个有序数组，然后再计算中位数。因为中位数的位置和m+n的奇偶性相关。如果为奇数，中文数下标为(m+n)/2;如果是偶数，中位数和两个数有关，下标依次为：(m+n-1)/2, (m+n)/2。比如[1,2,3]，中位数是2；[1,2,3,4]，中位数是2.5。但是这种做法时间复杂度比较高，O(m+n)。不符合时间复杂度要求。

正确解法是使用二分查找。

数组1大小为m，数组2大小为n；m和n的大小不一定，可能数组1容量大，也可能数组2容量大，也可能两个数组长度相同。这里使用一个trick，直接查找在merged后第k大的数，直接找到和中位数相关的数。因为m+n奇偶性不一定，我们直接查找(m+n+1)/2, (m+n+2)/2大的数。可以验证，如果(m+n)是奇数，(m+n+1)/2和(m+n+2)/2大小相等[(m+n+2)/2 = (m+n+1 + 1)/2 = (m+n+1)/2 + 1/2 = (m+n+1)/2]；如果是偶数，那么(m+n+1)/2和(m+n+2)/2正好是和中位数相关的两个数。

接下来的问题就是，给定一个数k如何找到merged后的第k个数。先考虑边界情况：

  • 如果一个数组为空，那么在第k个数一定在另一个数组里[因为题题目要求，两个数组不能同时为空，所以一定在另一个数组里]
  • 如果k为1，那么结果一定是两个数组中第一个元素较小的那一个。

一般情况，两个数组都不为空，同时k也不为1，那么如何在两个有序数组中找到第k个数呢？二分查找，如何应用在两个数组里？这里，采用一种独特的二分查找方法，对查找数k进行二分, 一般情况下是对有序数组范围进行二分；(接下来的问题就是边界的变化)分别在两个数组里找第k/2个数，如果第k/2个数的位置超出了数组范围，返回一个无效值；如果有效，比较两个数组中的查找结果midVal1和midVal2：如果midVal1 < midVal2，那么第k大的数一定不在midVal1的左边，所以，我们对数组1的有效范围进行缩小，同时在数组1的剩余元素和数组2中继续查找，查找第k-k/2个数[抛去了k/2个元素，这些元素一定是在第k个元素之前，所以需要查找的数也要对应减小；另外，这里必须使用k-k/2,不能直接使用k/2，因为k有可能是偶数，k/2的结果一定是整型，导致结果出错]。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int left = (m + n + 1)/2, right = (m + n + 2)/2;
        
        return (find(nums1, 0, nums2, 0, left) + find(nums1, 0, nums2, 0, right))/2.0;
    }
    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k){
        if (i >= nums1.size()) return nums2[j + k - 1];
        if (j >= nums2.size()) return nums1[i + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        
        int midVal1 = (i + k / 2 - 1 >= nums1.size() ? INT_MAX : nums1[i + k/2 - 1]);
        int midVal2 = (j + k/2 -1 >= nums2.size() ? INT_MAX : nums2[j + k / 2 - 1]);
        
        if (midVal1 < midVal2)
            return find(nums1, i + k/2, nums2, j, k - k/2);
        else
            return find(nums1, i, nums2, j + k/2, k - k/2);
    }
};

Reference

https://www.cnblogs.com/grandyang/p/4465932.html

您的支持就是我更新的最大动力!谢谢!