Leetcode系列之链表（16）

题目：

有两个大小分别为m和n的有序数组A和B。请找出这两个数组的中位数。你需要给出时间复杂度在O(log (m+n))以内的算法。

思路：

1.使用数组的归并不能满足时间复杂度的要求

2.采用分治思想

3.关键在于优化算法以满足时间复杂度

代码：

public class Solution {

    public double findMedianSortedArrays(int A[], int B[]) {

        if(A.length > B.length){

            return findMedianSortedArrays(B, A);

        }

        int cut1=0;

        int cut2=0;

        int len = A.length+B.length;

        int cutL = 0;

        int cutR = A.length;

        while(cut1 <=A.length){

            cut1 = (cutR-cutL)/2 + cutL;

            cut2 = len/2 - cut1;

            double left1 = (cut1==0)?Integer.MIN_VALUE:A[cut1-1];

            double left2 = (cut2==0)?Integer.MIN_VALUE:B[cut2-1];

            double right1 = (cut1==A.length)?Integer.MAX_VALUE:A[cut1];

            double right2 = (cut2==B.length)?Integer.MAX_VALUE:B[cut2];

            if(left1 > right2){

                cutR = cut1 -1;

            }else if(left2 > right1){

                cutL = cut1+1;

            }else{

                if(len % 2 == 0){

                    left1 = left1 > left2 ? left1:left2;

                    right1 = right1 > right2 ? right2 : right1;

                    return ( left1 + right1 )/2;

                }else{

                    right1 = (right1 > right2 ? right2 : right1);

                    return right1;

                }

            }

        }

        return -1;

    }

}