`
vvaaiinn
  • 浏览: 21516 次
  • 性别: Icon_minigender_1
  • 来自: 大连
文章分类
社区版块
存档分类
最新评论

leetcode 4 Median of Two Sorted Arrays

 
阅读更多

题目:There are two sorted arrays A and B 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)).

看到题目,首先想到的是 把2个数组合并成一个,然后在去中间位置的数字。

后来发现时间复杂度为O(m+n);与题目不符合。

找了一些前辈的解题思路后自己模仿写了一个解法,并附上自己的理解。


代码:

public class Solution {
     public double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;
        int total = m + n;
        if(total%2==1)//如果是奇数,返回中间total/2 ,至于为何加1,我感觉是为了防止越界。
        {
        	return findMed(A, m, B, n, total/2+1);
        }
        else //如果是偶数,返回中间2个的平均数
        {
        	return (findMed(A, m, B, n, total/2)+findMed(A, m, B, n, total/2+1))/2;
        }
   }
	
    public double findMed(int A[],int m,int B[],int n,int median)
    {
    	if(m == 0)//如果是空,返回另一个的中位数
    	{
    		return B[median-1]; 
    	}
    	else if(n == 0)
    	{
    		return A[median-1];
    	}
    	else if(median == 1)//如果是第1个,则取这2个数的最小的为中位数
    	{
    		return Math.min(A[0],B[0]);
    	}
    	else if(m > n)//保证前面的是个数最小的数字 防止出现 A个数为2 B个数为8 median为8 median/2 大于2 数组会越界。
    	{
    		return findMed(B, n, A, m, median);
    	}
    	int am = Math.min(m, median/2);
    	int bm = median - am;
    	if(A[am-1] < B[bm-1])
    	{
    		return findMed(Arrays.copyOfRange(A, am, m), m-am, B, n, median-am);
    	}
    	else if(A[am-1]>B[bm-1])
    	{
    		return findMed(A, m, Arrays.copyOfRange(B, bm, n), n-bm, median-bm);
    	}
    	else return A[am-1];
    }
    	
}

二分查找,当计算m+n/2的时候,则可能出现越界的问题。

这个时候可以用n+ (m-n)/2,前提m>n来避免这种问题出现。

虽说是个不起眼的小技巧,不过以前还真没注意到。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics