Cinte's Leetcode Record
0%

4. Median of Two Sorted Arrays

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

4. Median of Two Sorted Arrays

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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        // 有必要保证在短的上面遍历，如果在长的上的话
        // j = (m + n + 1) / 2 - i中 i可能>n，则j可能<0
        if(m > n)
        {
            nums1.swap(nums2);
            swap(m, n);
        }
        if(m == 0)
            return (n & 1) ? (nums2[n / 2]) : (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
        int lo = 0, hi = m; // 为了让结果可以靠向m，这里的hi需要定义为m
        while(lo <= hi)  // 相等后进入最后计算一次，然后得出解
        {
            int i = lo + (hi - lo) / 2, j = (m + n + 1) / 2 - i; // 推导过程中假设是奇数的情况让左边多一个，则i + j = m + n - i - j，如果是偶数那就相同，此时由于这个除法是向下取整的，所以偶数和奇数情况可以合并
            if(i > 0 && nums1[i - 1] > nums2[j]) // 本来是需要i>0 && j < n，但是由于满足n >= m，当i > 0时，j = (m + n + 1) / 2 - i <= (m + n + 1) / 2 <= (m + n + 1) / 2 <= m + 1/2 < m
                hi = i - 1;
            else if(i < m && nums2[j - 1] > nums1[i]) // j > 0 && i < m, 同上证明
                lo = i + 1;
            else
            {
                // 几种边缘情况处理
                int left, right;

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

                if((m + n) & 1) // 假设的是左半边多一个
                    return left;

                if(i == m)
                    right = nums2[j];
                else if(j == n)
                    right = nums1[i];
                else
                    right = min(nums1[i], nums2[j]);

                return (left + right) / 2.0;
            }
        }
        return 0;
    }
};