首页 > 代码库 > Median of Two Sorted Arrays(Java)

Median of Two Sorted Arrays(Java)

求2个数组的中位数

方法很多

但是时间复杂度各异

 

1利用数组copy方法先融合两个数组,然后排序,找出中位数

import java.lang.reflect.Array;import java.util.Arrays;import java.util.Collection;import java.util.Collections;public class _004MedianofTwoSortedArrays {    public static void main(String[] args)    {            int a[]={2,3,5,9};        int b[]={1,4,7,10,11};        System.out.println(findMedianSortedArrays(a,b));    }         public static double findMedianSortedArrays(int A[], int B[])      {         int[] d3 = new int[A.length + B.length];         System.arraycopy(A, 0, d3, 0, A.length);         System.arraycopy(B, 0, d3, A.length, B.length);         Arrays.sort(d3);         System.out.println(Arrays.toString(d3));         return d3.length%2!=0?d3[d3.length/2]/1.0:(d3[d3.length/2-1]+d3[d3.length/2])/2.0;                 }     }

 

2是循环判断插入新数组中 等于说不用内置copy方法自己写一个替代

 1 import java.util.Arrays; 2  3  4 public class _004_2Median { 5  6     public static void main(String[] args) { 7         // TODO Auto-generated method stub 8         int a[]={2,34}; 9         int b[]={1,4,9};10         System.out.println(findMedianSortedArrays(a,b));11     }12 13     private static double findMedianSortedArrays(int[] a, int[] b) {14         int k=a.length+b.length;15         System.out.println(k);16         int[] c=new int[k];17         int i=0,j=0,m=0;18         while(m!=k)19         {20             if(i==a.length)21             {22                 c[m]=b[j];23                 j++;24                 25             }26             else if(j==b.length)27             {28                 c[m]=a[i];29                 i++;30             }31             else if(a[i]<b[j])32             {33                 c[m]=a[i];34                 i++;35             36             }37             else 38             {39                 c[m]=b[j];40                 j++;41                 42                 43             }44             m++;45         }46         47         return k%2==0?(c[k/2-1]+c[k/2])/2.0:c[k/2]/1.0;48         49     }50 51 }

 

3第三种递归方法有待研究

Median of Two Sorted Arrays(Java)