LeetCode4---两个排序数组的中位数

有两个大小为 m 和 n 的排序数组 nums1 和 nums2 。

请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。

示例 1:

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5

分析：给两个排序好的数组，长度分别为m和n，在（m+n）/2时间复杂度内找出中位数。因为是排好序的数组，指定两个游标，初始分别在两个数组的开头，比较两个数组游标所在位置的数值大小，小的放进队列，然后移动游标。当队列内的数量大于(m+n)>>1时，就可以得到中位数了，一共需要访问（m+n）>>2个元素，符合时间复杂度要求，注意处理一些特殊情况就好。

/**
队列用的LinkedList，因为只需要末尾添加元素同时末尾取元素，所以LinkedList的效率更加优秀。从oj的时间反馈也可以看出来，因为ArrayLIst中间会有扩容的操作，所以LinkedList更加合适
**/

private double getSingleArrayMidle(int[] nums2, boolean isSingle){
        if (isSingle){
            return nums2[nums2.length>>1];
        }else {
            int m = nums2[nums2.length>>1];
            int n = nums2[(nums2.length>>1) - 1];
            return (m+n)/2.0;
        }
    }
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //获取总长度
        int sumLen = nums1.length + nums2.length;
        //判断总数是奇数还是偶数
        boolean isSingle = (sumLen&1) == 1;
        if (sumLen == 0){
            return 0;
        }
        //nums1为空
        if (nums1.length == 0){
            return getSingleArrayMidle(nums2, isSingle);
        }
        //nums2为空
        if (nums2.length == 0){
            return getSingleArrayMidle(nums1, isSingle);
        }

        LinkedList<Integer> linkedList = new LinkedList<>();
        int curPos1 = 0;
        int curPos2 = 0;
        while (linkedList.size() <= (sumLen>>1)){
            if (curPos1 >= nums1.length){
                linkedList.add(nums2[curPos2]);
                curPos2++;
                continue;
            }
            if (curPos2 >= nums2.length){
                linkedList.add(nums1[curPos1]);
                curPos1++;
                continue;
            }
            if (nums1[curPos1] > nums2[curPos2]){
                linkedList.add(nums2[curPos2]);
                curPos2++;
            }else {
                linkedList.add(nums1[curPos1]);
                curPos1++;
            }
        }
        //奇数长度
        if ((sumLen&1) == 1){
            return linkedList.getLast();
        }

        //偶数长度
        int m = linkedList.getLast();
        linkedList.removeLast();
        int n = linkedList.getLast();
        return (m+n)/2.0;
    }