|
| 1 | +/* |
| 2 | + Author: King, wangjingui@outlook.com |
| 3 | + Date: Dec 12, 2014 |
| 4 | + Problem: Median of Two Sorted Arrays |
| 5 | + Difficulty: Hard |
| 6 | + Source: http://leetcode.com/onlinejudge#question_4 |
| 7 | + Notes: |
| 8 | + There are two sorted arrays A and B of size m and n respectively. |
| 9 | + Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). |
| 10 | +
|
| 11 | + Solution: 1. O(m+n) |
| 12 | + 2. O(log(m+n)) |
| 13 | +*/ |
| 14 | + |
| 15 | +publicclassSolution { |
| 16 | +publicdoublefindMedianSortedArrays_1(intA[],intB[]) { |
| 17 | +intm =A.length,n =B.length; |
| 18 | +inttotal =n +m,m1=0,m2=0,i=0,j=0; |
| 19 | +for (intk =1;k <=total/2 +1; ++k) { |
| 20 | +inta = (i==m) ?Integer.MAX_VALUE :A[i]; |
| 21 | +intb = (j==n) ?Integer.MAX_VALUE :B[j]; |
| 22 | +m1 =m2; |
| 23 | +m2 =Math.min(a,b); |
| 24 | +if (a >b) ++j; |
| 25 | +else ++i; |
| 26 | + } |
| 27 | +if ((total&1) ==1)returnm2; |
| 28 | +elsereturn (m1+m2)/2.0; |
| 29 | + } |
| 30 | +publicdoublefindMedianSortedArrays_2(intA[],intB[]) { |
| 31 | +intm =A.length,n =B.length; |
| 32 | +inttotal =m +n; |
| 33 | +intk =total /2; |
| 34 | +if ((total&1) ==1)returnfindKth(A,B,k+1,0,m-1,0,n-1); |
| 35 | +elsereturn (findKth(A,B,k,0,m-1,0,n-1)+findKth(A,B,k+1,0,m-1,0,n-1))/2.0; |
| 36 | + } |
| 37 | +publicdoublefindKth(intA[],intB[],intk,intastart,intaend,intbstart,intbend) { |
| 38 | +intalen =aend -astart +1; |
| 39 | +intblen =bend -bstart +1; |
| 40 | +if (alen >blen)returnfindKth(B,A,k,bstart,bend,astart,aend); |
| 41 | +if (alen ==0)returnB[bstart +k -1]; |
| 42 | +if (k ==1)returnMath.min(A[astart],B[bstart]); |
| 43 | +intsa =Math.min(alen,k/2),sb =k-sa; |
| 44 | +if (A[astart+sa-1] ==B[bstart+sb-1])returnA[astart+sa-1]; |
| 45 | +elseif (A[astart+sa-1] >B[bstart+sb-1])returnfindKth(A,B,k -sb,astart,aend,bstart+sb,bend); |
| 46 | +elsereturnfindKth(A,B,k -sa,astart+sa,aend,bstart,bend); |
| 47 | + } |
| 48 | + |
| 49 | +} |
