【LeetCode】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

public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int len1=nums1.length;

        int len2=nums2.length;

        int k=len1+len2;

        if(k%2!=0){

           return findMedian(nums1,0,len1,nums2,0,len2,k/2+1);

        }else{

            return (findMedian(nums1,0,len1,nums2,0,len2,k/2)+findMedian(nums1,0,len1,nums2,0,len2,k/2+1))/2;

        }

    }

    public static double findMedian(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k ){

        if(end1>end2){

            return findMedian(nums2,start2,end2,nums1,start1,end1,k);

        }

        if(end1<=0){

            return nums2[start2+k-1];

        }

        if(k==1){

            return Math.min(nums1[start1],nums2[start2]);

        }

        int k1=Math.min(k/2,end1);

        int k2=k-k1;

        if(nums1[start1+k1-1]<nums2[start2+k2-1]){

            return findMedian(nums1,start1+k1,end1-k1,nums2,start2,end2,k-k1);

        }else{

            return findMedian(nums1,start1,end1,nums2,start2+k2,end2-k2,k-k2);

        }

    }

}

巴特西

【LeetCode】4.Median of Two Sorted Arrays 两个有序数组中位数

最新文章

热门文章