本文共 2627 字,大约阅读时间需要 8 分钟。
算法步骤(基本原理是获取第k小的数) 先取两个中间索引x_mid,y_mid; 下面来比较 如果x[x_mid]比较小,那么就看x_mid最大是第几小(记作m) ①m
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { if(nums2.length==0){ if(nums1.length%2==0){ return (double) (nums1[(nums1.length-1)/2]+nums1[(nums1.length-1)/2+1])/2.0; }else return (double)nums1[(nums1.length-1)/2]; }else if(nums1.length==0){ if(nums2.length%2==0){ return (double) (nums2[(nums2.length-1)/2]+nums2[(nums2.length-1)/2+1])/2.0; }else return (double)nums2[(nums2.length-1)/2]; } int i; if((nums1.length+nums2.length)%2==0){ i=(nums1.length+nums2.length)/2; return (get_Middle_num(nums1,0,nums1.length-1,nums2,0,nums2.length-1,i) +get_Middle_num(nums1,0,nums1.length-1,nums2,0,nums2.length-1,i+1))/2.0; } else{ i=(nums1.length+nums2.length)/2+1; return (double)get_Middle_num(nums1,0,nums1.length-1,nums2,0,nums2.length-1,i); } } int get_Middle_num(int x[],int left_x,int right_x,int y[],int left_y,int right_y,int k){ */ if(left_x>right_x){ return y[left_y+k-1]; }else if(left_y>right_y){ return x[left_x+k-1]; }else if(k==1){ return x[left_x]>y[left_y]?y[left_y]:x[left_x]; }else{ int x_mid = (left_x+right_x)/2; int y_mid = (left_y+right_y)/2; int num = (x_mid-left_x)+(y_mid-left_y); //注意num+1代表含义:x_mid可以到达的最大第几小 // num+2代表含义:y_mid可以到达的最小第几小 if(x[x_mid]<=y[y_mid]){ //接下来我们开始锁定x左边界和y的右边界 if(num+2==k){ right_y=y_mid; }else if(num+2>k) right_y=y_mid-1; if(num+1k) right_x=x_mid-1; if(num+1
算法复杂度分析:
T(n)=T(n/4)+O(1) O(n)=logn 最后附上测试用例来供读者使用@Test public void Test(){ //[76,89,104,30823,31070,31259,31324,31714,31971,320331] //[122,2919,2941,17754,17781,17830,17874,18019,18023,18130] //[2634,2764,2801,30823,31070,31259,32319,32350,32408,32475,32681,32701,32764] //[122,32605,32641,32716,32757] int x[]={ 2634,2764,2801,30823,31070,31259,32319,32350,32408,32475,32681,32701,32764}; int y[]={ 122,32605,32641,32716,32757}; System.out.println(get_Middle_num(x,0,x.length-1,y,0,y.length-1,1)); System.out.println((x.length+y.length)); }
转载地址:http://yvlzi.baihongyu.com/