Leetcode 4. Median of Two Sorted Arrays

发表于 | 分类于

https://leetcode.com/problems/median-of-two-sorted-arrays/

这道题的题意是给定两个已经排好序的数组，求这两个数组所有数字的中位数，要求时间复杂度是O(log(m+n))的（应该自然想到
是二分法）

这道题感觉有点难，看了半天代码也看不懂是什么意思。。。，不过这样的题确实有意思。。。

思路： 在两个数组中找两个分解点i，j，保证0～i-1加0～j-1是两个数组的长度之和的一半，目标就是确定i和j的位置，使得
i-1位置数字也小于j位置数字（i-1位置数字保证小于i位置数字）和j-1位置数字小于i位置数字，这样0～i-1和0～j-1位置所有
数字都小于另一半部分的数字，中位数就是i-1和j-1位置数字的较大值和i位置和j位置数字的较小值的均值（两个数组所有数字
个数是偶数的话），或者i-1和j-1位置数字的较大值

代码：

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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if(m > n)
            return findMedianSortedArrays(nums2, nums1);
        
        int left = 0, right = m;
        int i = -1, j = -1;
        while(true){
            i = (left + right) / 2;
            j = (m + n + 1) / 2 - i;
            
            if((i == 0 || j == n || nums1[i - 1] <= nums2[j]) && 
               (j == 0 || i == m || nums2[j - 1] <= nums1[i])){
                break;
            }
            else if(i > 0 && nums1[i-1] > nums2[j]){
                right = i - 1;
            }
            else if(j > 0 && nums2[j-1] > nums1[i]){
                left = i + 1;
            }
        }
        
        int max_left = -1, min_right = -1;
        if(i == 0){
            max_left = nums2[j-1];
        }
        else if(j == 0){
            max_left = nums1[i-1];
        }
        else{
            max_left = max(nums1[i - 1], nums2[j - 1]);
        }
        
        if((m+n) % 2){
            return max_left;
        }
        
        if(i == m) 
            min_right = nums2[j];
        else if(j == n) 
            min_right = nums1[i];
        else{
            min_right = min(nums1[i], nums2[j]);
        }
        
        return double(max_left + min_right) / 2;
    }
};

0%