Poison

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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        // 寻找中位数的分界线，搜索目标：右侧数组的起始元素索引，当右侧数组为空时，索引停留在 nums1.length
        // 也可理解为左侧数组元素的个数
        int left = 0, right = nums1.length;
        // [0, nums1Mid - 1] | [nums1Mid, nums1.length - 1]
        // [0, nums2Mid - 1] | [nums2Mid, nums2.length - 1]

        //        | [2]
        // [1, 3] | 

        //        | [1, 2]
        // [3, 4] |

        int median1 = 0, median2 = 0;
        while (left <= right) {
            int nums1Mid = (left + right) >>> 1;
            // 注意此处移位操作需要加括号，因为移位运算符优先级低于加减法
            int nums2Mid = ((nums1.length + nums2.length + 1) >>> 1) - nums1Mid; // 当两个数组的总元素个数为奇数时，保证多的那个元素位于分界线左侧

            // ... n1Left n1Right ...
            // ... n2Left n2Right ...
            int nums1Left = nums1Mid - 1 < 0 ? Integer.MIN_VALUE : nums1[nums1Mid - 1];
            int nums1Right = nums1Mid == nums1.length ? Integer.MAX_VALUE : nums1[nums1Mid];
            int nums2Left = nums2Mid - 1 < 0 ? Integer.MIN_VALUE : nums2[nums2Mid - 1];
            int nums2Right = nums2Mid == nums2.length ? Integer.MAX_VALUE : nums2[nums2Mid];
            if (nums1Left <= nums2Right) {
                // 可能是中位数，记录中位数并继续收缩
                median1 = Math.max(nums1Left, nums2Left);
                median2 = Math.min(nums1Right, nums2Right);
                left = nums1Mid + 1;
            } else {
                right = nums1Mid - 1;
            }
        }

        if (((nums1.length + nums2.length) & 1) == 0) {
            return (median1 + median2) / 2.0;
        } else {
            return median1;
        }
    }
}
Reference

4. Median of Two Sorted Arrays