算法

Leetcode 4. Median of Two Sorted Arrays

Posted by Meng Cao on 2019-06-14

以一题多解为荣，以做出来就行为耻。

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

递归写法：

采用分治的思想来解决这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
每次删除k/2个元素，比较nums1和nums2的k/2个元素，删除小的那组；
可以用反证法证明小的那组不可能组成中位数
总结：
find k-th number in two sorted array
index  0  1  2  3  4   5   6   7   8
array1 1  3  5  7  9   11  12  13  14
array2 2  4  6  8  10
1. delete k/2 numbers in one array.
k==7, 两组各去k/2=3个数字，删掉1,3,5还是2，4，6？
删掉最大值小的，也就是删掉1,3,5.
2. prof k/2 deleted numbers not target k-th
反证法：如果5为7-th的数字，因为6>5,则array2中只有2个数字<5, array1中有2个数字小于5，达不到7个
3. 如果数组array1的长度不足k/2, 那么直接划掉另一个数组array2的前k/2元素。
(array1已倾其所有，但是和array2的前k/2还不能构成前k个，所以k-th元素必然在array的前k/2之后)
*/


class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        return ((double)(findKth(nums1, 0, nums2, 0, (m+n+1)/2)) + 
               (double)(findKth(nums1, 0, nums2, 0, (m+n+2)/2))) / 2.0;
    }
    
private:
    int findKth(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 mid1 = (i+k/2-1<nums1.size()) ? nums1[i+k/2-1] : INT_MAX;
        int mid2 = (j+k/2-1<nums2.size()) ? nums2[j+k/2-1] : INT_MAX;
        
        if(mid1 < mid2)
            return findKth(nums1, i+k/2, nums2, j, k-k/2);
        else
            return findKth(nums1, i, nums2, j+k/2, k-k/2);
    }
};

递推写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//O(log(min(m,n)))
/*
L1 R1
3 | 5  8  9
         L2   R2
1  2  7  10 | 11  12

总体思路：固定array1切割的位置p1，那么array2切割的位置也就确定size/2-p1
因为切割的时候已经保证了切割nums1左边和nums2左边之和为size/2,
所以只要保证左边两段小于右边两段即可：(L1 <= R1, L2 <= R2必然满足)
L1 <= R2
L2 <= R1
如果L1 > R2，则说明L1切割左边过多，二分搜索的边界向左，[curL, m1-1]
如果L2 > R2，则说明L1切割左边过少，二分搜索的边界向右, [m1+1, curR]
*/
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        if(n1 > n2)
            return findMedianSortedArrays(nums2, nums1);//总是保证前面的数组长度小于后面
        
        if(n1 == 0)//如果短数组为空
            return (nums2[(n2-1)/2] + nums2[n2/2]) / 2.0;//若n2为偶数，(n2-1)/2为中间偏左，n2/2为中间偏右；若n2位奇数，则(n2-1)/2==n2/2
        
        int size = n1 + n2;
        int cutL = 0, cutR = n1;//在nums1数组中二分查找要切割多少数字
        
        while(cutL <= cutR) {
            int m1 = cutL + (cutR-cutL)/2;
            int m2 = size/2 - m1;
            
            double L1 = (m1==0) ? INT_MIN : nums1[m1-1];
            double L2 = (m2==0) ? INT_MIN : nums2[m2-1];
            double R1 = (m1==n1) ? INT_MAX : nums1[m1];
            double R2 = (m2==n2) ? INT_MAX : nums2[m2];
            
            if(L1 > R2)
                cutR = m1 - 1;
            else if(L2 > R1)
                cutL = m1 + 1;
            else{
                if(size % 2 == 0){
                    L1 = (L1 > L2 ? L1 : L2);//L1, L2中较大值作为左中位数
                    R1 = (R1 < R2 ? R1 : R2);//R1, R2中较小值作为右中位数
                    return (L1+R1) / 2.0;
                }else
                    return (R1 < R2 ? R1 : R2);
            }
        }
        return -1;
    }
};
FEATURED TAGS
算法
FRIENDS