4、Median of Two Sorted Arrays

题设

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)).

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

要点

• 双有序数组

这道题其实没什么思路，因为限制了O(log(m + n))，不能暴力。
其实log(m + n)已经意味着使用二分法了(二分一个大小为n的数组最大时间复杂度为O(log(n)))。
也是太久没接触数据结构了，典型的时间复杂度都忘了。
最后参考了答案的解法，还纠结了半天，踉踉跄跄写出来。
学习了。

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

    public static double findMidianSortedArrays(int[] nums1 , int[] nums2){
        int len1 = nums1.length;
        int len2 = nums2.length;
        // 第一步，保证m≤n
        int a[];
        int b[];
        int m , n;
        if(len1 <= len2){
            a = nums1;
            b = nums2;
            m = len1;
            n = len2;
        }
        else{
            a = nums2;
            b = nums1;
            m = len2;
            n = len1;
        }
        // 现在，较短的数组为a，长为m；较长的数组为b，长为n
        // 进行二分
        int iLeft = 0, iRight = m; // 代表总共有多少个数进行二分，最多m个
        int i = 0 , j = 0;
        while(iLeft <= iRight){
            i = (iLeft + iRight) / 2;
            j = (m + n + 1) / 2 - i; // 保证i+j=总长度的一半
            
            if(i > iLeft && a[i - 1] > b[j]){ // i太大了
                iRight = i - 1;
            }
            else if (i < iRight && b[j - 1] > a[i]) { // i太小了
                iLeft = i + 1;
            }
            else { // 符合条件
                int maxLeft = 0; // 左边的最大值
                int minRight = 0; // 右边的最小值
                
                if(i == 0){
                    maxLeft = b[j - 1];
                }
                else if(j == 0){
                    maxLeft = a[i - 1];
                }
                else {
                    maxLeft = Math.max(a[i - 1], b[j - 1]);
                }
                
                if((m + n) % 2 == 1) // 左边的最大值正好是中位数
                    return maxLeft;
                else{
                    if(i == m){ // 这是iLeft不断右移到头的情况，有b[j - 1] > a[i]
                        minRight = b[j];
                    }
                    else if(j == n){ // 这是iRight不断左移到头的情况，有a[i - 1] > b[j]
                        minRight = a[i];
                    }
                    else {
                        minRight = Math.min(b[j], a[i]);
                    }
                    return (maxLeft + minRight) / 2.0;
                }
            }
        }
        return 0.0;
    }