1

我刚刚测试了自己实现两个排序数组的中位数，如下所述：http ://www.youtube.com/watch?v=_H50Ir-Tves 。这个实现正确吗？先感谢您。卡塔琳娜

PS：算法 compute() 为传递的数组返回 7。如果我合并两个数组并通过直接调用 median() 方法检测中值，则再次返回值 7。所以我假设这个算法行为正确，但可能存在一些边界情况和情况，当它不起作用时。你能给我反馈一下这个实现是否正确吗？

公共类中位数{

public static class MedianDetector {

    public MedianDetector() {}

    public int median( int[] arr) {
        if( arr.length == 1 ) return 0;
        int rest = arr.length%2;
        return arr.length/2+rest;       
    }

    public int compute( int[] a, int[] b ) {
        int aMed = median(a);
        int bMed = (a.length+b.length)/2-aMed; //median finding formula

        if( a.length == 1)
            return a[0];
        if( b.length == 1) 
            return b[0];

        if( b[bMed] <= a[aMed] && a[aMed] <= b[bMed+1] ) {
            return a[aMed];
        } else
        if( a[aMed] <= b[bMed] && b[bMed] <= b[bMed+1] ) {
            int[] _a = new int[ a.length - aMed -1 ]; 
            System.arraycopy(a, aMed+1, _a, 0, _a.length);  
            int[] _b = new int[ bMed];
            System.arraycopy(b, 0, _b, 0, _b.length);   
            return compute( _a, _b);
        } else
        if( b[bMed] <= b[bMed+1] && b[bMed+1] <= a[aMed]) {
            int[] _a = new int[ aMed];
            System.arraycopy(a, 0, _a, 0, _a.length);
            int[] _b = new int[b.length - bMed-1];
            System.arraycopy(b, bMed+1, _b, 0, _b.length);
            return compute( _a, _b);                
        } else{
            throw new RuntimeException();
        }
    }

}

public static void main(String[] args) {

    int[] a = new int[] {1,2,3,3,3,3,4,5,6,7,8,9,9,9,9};
    int[] b = new int[] {5,6,7,8,8,8,9};                                
    System.out.println( (new MedianDetector()).compute(a,b) );  //returns 7

    int[] total = new int[a.length+b.length];
    System.arraycopy(a,0,total,0,a.length);
    System.arraycopy(b,0,total,a.length,b.length);
    //total list: [1, 2, 3, 3, 3, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9]

    List<Integer> totalList = new ArrayList<Integer>();
    for( int t : total )
        totalList.add(t);
    Collections.sort(totalList);
    System.out.println(totalList);      
    System.out.println( (new MedianDetector()).median(total) );
    System.out.println( totalList.get( (new MedianDetector()).median(total) ) ); //returns 7 as well
}

}

4

0 回答 0