首页 > 代码库 > 【LeetCode】median of two sorted arrays
【LeetCode】median of two sorted arrays
题目:median of two sorted arrays
知识点:二分查找,中位数定义
public class Solution { /* * 关于:leetcode 第二题 给定两个排好序的数组。找到它们的中位数,要求:时间复杂度o(log(m+n)); * 变形:找第k个数 * 方法:1.遍历。时间复杂度为o(m+n),从头開始分别遍历两数组的数,依照大小计数,直到第k个数 * 2.递归,由于两个数组是排好序的。所以先各取第k/2的数比較,小的一边必定全都在第k个数之前(反证法) * 大的一边则可能不全在k前,于是递归再找剩下的k/2个数。 * 返回条件:1.一个数组为空时,直接返回还有一个数组第k个数 * 2.k=1,返回min(A[0],B[0]) * 3.A[k/2-1] == B[k/2-1],返回当中一个的值 */ public double findMedianSortedArrays(int A[], int B[]) { int n = A.length; int m = B.length; int total = n+m; if(total%2 == 1){ //假设两个数组的个数相加是奇数。不能有total&0x1推断。。 return culMedian(A,n,B,m,total/2+1); } else return (culMedian(A,n,B,m,total/2)+culMedian(A,n,B,m,total/2+1))/2.0; } public double culMedian(int A[],int n,int B[],int m,int k){ if(n == 0) return B[k-1]; if(m==0) return A[k-1]; if(k == 1) return A[0]<B[0]?A[0]:B[0]; int a = k/2 < n ? k/2 : n; //注意边界条件的考虑 int b = k-a < m ?k-a : m; if(A[a-1] < B[b-1]){ //java不能直接用A+a传递指针。。。还有别的方法吗??? int iA[] = new int[n-a]; for(int i = a;i < n;i++) iA[i-a] = A[i]; return culMedian(iA,n-a,B,m,k-a); } else if(A[a-1] > B[b-1]){ int iB[] = new int[m-b]; for(int i = b;i < m;i++) iB[i-b] = B[i]; return culMedian(A,n,iB,m-b,k-b); } else return A[a-1]; } }
【LeetCode】median of two sorted arrays
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。