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
}
}