|
| 1 | +packageAlgorithms.array; |
| 2 | + |
| 3 | +publicclassFindMedianSortedArrays { |
| 4 | +publicstaticvoidmain(String[]strs) { |
| 5 | +intA[] = {100000}; |
| 6 | +intB[] = {100001}; |
| 7 | + |
| 8 | +System.out.println(findMedianSortedArrays(A,B)); |
| 9 | + } |
| 10 | + |
| 11 | +publicstaticdoublefindMedianSortedArrays(intA[],intB[]) { |
| 12 | +if (A ==null ||B ==null) { |
| 13 | +return0; |
| 14 | + } |
| 15 | + |
| 16 | +intlen =A.length +B.length; |
| 17 | + |
| 18 | +doubleret =0; |
| 19 | +// 偶数个元素 |
| 20 | +if (len %2 ==0) { |
| 21 | +ret = (findKth(A,B,0,0,len /2) +findKth(A,B,0,0,len /2 +1)) / (double)2.0; |
| 22 | + }else { |
| 23 | +// 奇数个元素 |
| 24 | +ret =findKth(A,B,0,0,len /2 +1); |
| 25 | + } |
| 26 | + |
| 27 | +returnret; |
| 28 | + } |
| 29 | + |
| 30 | +// Find the Kth large number. |
| 31 | +publicstaticintfindKth(intA[],intB[],intindexA,intindexB,intk) { |
| 32 | +intlenA =A.length; |
| 33 | +intlenB =B.length; |
| 34 | + |
| 35 | +if (indexA >=lenA) { |
| 36 | +returnB[indexB +k -1]; |
| 37 | + }elseif (indexB >=lenB) { |
| 38 | +returnA[indexA +k -1]; |
| 39 | + } |
| 40 | + |
| 41 | +// Base Case, pay attention. 在这里必须要退出。因为k = 1的时候，不可能再分了。 |
| 42 | +if (k ==1) { |
| 43 | +returnMath.min(A[indexA],B[indexB]); |
| 44 | + } |
| 45 | + |
| 46 | +// -1是因为索引本身是从0开始的。而前k大元素含有k个元素。 |
| 47 | +intmid =k /2 -1; |
| 48 | + |
| 49 | +// 注意，越界条件是 >= lenA. 怎么老是犯这个错误。。 |
| 50 | +intkeyA =indexA +mid >=lenA ?Integer.MAX_VALUE:A[indexA +mid]; |
| 51 | +intkeyB =indexB +mid >=lenB ?Integer.MAX_VALUE:B[indexB +mid]; |
| 52 | + |
| 53 | +// 因为丢弃了k / 2个元素 |
| 54 | +intkNew =k -k /2; |
| 55 | + |
| 56 | +if (keyA <keyB) { |
| 57 | +returnfindKth(A,B,indexA +k /2,indexB,kNew); |
| 58 | + }else { |
| 59 | +returnfindKth(A,B,indexA,indexB +k /2,kNew); |
| 60 | + } |
| 61 | + } |
| 62 | +} |