【leetcode hot 100 4】寻找两个正序数组的中位数

解法一：（双指针）用双指针顺序逐步加入新的数组，时间复杂度O(m+n)，空间复杂度O(m+n)

解法二：（二分查找）找这两个数组的分割线，保证：分割线的左边个数=分割线的右边个数or分割线的左边个数+1=分割线的右边个数。于是中位数应该为：偶数情况，（左边最大值+右边最小值）/2；奇数情况，分割线左边最大数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 先把短的那个数组放前面
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        // 记录两个数组的长度
        int m = nums1.length;
        int n = nums2.length;
        // 取左边的个数（分割线在中间or中间元素的右边）
        int totalLeft = (m + n + 1) / 2;
        // 以第一个数组来找分割线
        int left = 0, right = m;  // 这里的right=m而不是right=m-1
        while (left < right) {
            int i = (left + right) / 2; // 是第一各数组的分割线，nums[i-1]是左边的元素nums[i]是右边的元素
            int j = totalLeft - i;
            // 分割线必须满足：nums1[i-1]<=nums2[j] && nums2[j-1]<=nums1[i]
            // 我们拿第二个条件取反，来找循环的更新
            if (nums2[j - 1] > nums1[i]) {
                // 分割线应该在现在分割线的右边
                left = i + 1;
            } else {
                // 分割线在左边
                right = i;
            }
        }
        // 找到分割线left=right
        int i = left;
        int j = totalLeft - i;
        // 中位数应该为：偶数情况，（左边最大值+右边最小值）/2
        // 奇数情况，左边最大
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1]; // 要解决i-1数组越界的问题
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i]; // 要解决i数组越界的问题
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if ((m + n) % 2 == 1) {
            // 奇数情况
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))/ 2; // 要强转double，再除2保留小数
        }
    }
}

注意：

• int left = 0, right = m这里的right=m而不是right=m-1
• 在偶数情况下，(double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2 要强转为double，再除2保留小数
• 还有一种解法

while (left < right) {
	int i = (left + right+1) / 2; 
	int j = totalLeft - i;
	// 分割线必须满足：nums1[i-1]<=nums2[j] && nums2[j-1]<=nums1[i]
	// 我们拿第一个条件取反，来找循环的更新
	if (nums1[i-1]>nums2[j]) {
		// 分割线应该在现在分割线的左边
		right = i - 1;
	} else {
		// 分割线在右边
		left = i;  // 在这种情况下i=(left+right)/2和left=i有可能会死循环，改i = (left + right+1) / 2
	}
}