Median of Two Sorted Arrays
Something must know about Median
- odd: median of {3, 3, 5, 9, 11} is 5
- even: the median of {3, 5, 7, 9} is (5 + 7) / 2 = 6
Kth of two sorted array in O(log(m + n))
O(m + n)
Acting like Merge Sorted Array, just take first k
elements.
But, I will show you a brute force version, because it can be optimized to O(log(m + n))
easily.
O(m + n)
Brute Force
search through kth of Array M
and Array N
Code is like
foreach n in array m and array n
if isKth(n)
found
Core tech is how to determine if n
is the kth.
isKth
Imagine that take k
elements from Array M
and Array N
, m
elements from Array M
and n
from Array N
.
such that, the Kth
element must be MAX(mth of Array M, nth of Array N)
e.g.
Array M [1, 3, 5, 7, 9]
Array N [0, 2, 4, 6, 8]
Array M [1, 3, 5, 7, 9]
^
|
+-+
|
Array N [0, 2, 4, 6, 8]
try to put the nth element after the mth element
- take 3 elements from M:
[1, 3, 5]
- take 4(7-3) elements from N:
[0, 2, 4, 6]
- the 7th element is:
MAX(5,6)
- 8th..10th
[7, 8, 9]
are greater than or equals to the 7th
that is
- k = m + n
- kth = MAX(ArrayM[m], ArrayN[n])
- elements in
ArrayM[m + 1..end]
andArrayN[n + 1..end]
must be greater than or equals to the kth
So checking kth code is like
function isKth(m, ArrayM, ArrayN)
n = k - m
return ArrayN[n] <= ArrayM[m] <= ArrayN[n + 1]
O(log(m + n))
Binary Search
with isKth
, we can write a binary search version using binary search template.
search arrayM
while s < e
m = (s + e) / 2
if iskth(m, arrayM, arrayN)
return ArrayM[mid]
// solve this later
s = m + 1 or e = m
this will take O(log(m))
time, if kth is not found, do the same to ArrayN
.
s = m + 1 or e = m
when mid is not kth, we are going to remove half of the elements that must not contain the kth.
searching Array M
Array M [0, 2, 4, 6, 8]
s m e
Array N [1, 3, 5, 7, 9]
n
k = 7
n = k - m
- ArrayM[m] = 4
- ArrayN[n] = 7
If ArrayM[m]
is not the kth, that is, ArrayM[m]
is less than ArrayN[n]
or ArrayN[n + 1]
.
When ArrayM[m] < ArrayM[n]
, we must enlarge the ArrayM[m]
, so s = m + 1
if we want ArrayM[m]
to be the kth.
Similarly, we must diminish ArrayM[m] if ArrayM[m] > ArrayM[n]
In code:
if ArrayM[m] < ArrayM[n]
// enlarge ArrayM[m]
s = m + 1
else
// diminish ArrayM[m]
e = m
Put them together
len = len(A) + len(B)
if len is odd
kth(A,B, len/2)
else
(kth(A,B, len/2) + kth(A,B, len/2 + 1)) / 2
Note
- Array in my code start from
0
- Sometimes, no element on any index, just treat it as -INFINITE
Source code Read on Github
1 public class Solution {
2
3 int safe(int[] X, int i){
4
5 if ( i < 0) return Integer.MIN_VALUE;
6
7 if ( i >= X.length) return Integer.MAX_VALUE;
8
9 return X[i];
10 }
11
12 int kth(int[] A, int[] B, int k){
13
14 if (A.length == 0)
15 return B[k];
16
17 if (B.length == 0)
18 return A[k];
19
20 if (k == 0)
21 return Math.min(A[0], B[0]);
22
23 if (A.length == 1 && B.length == 1){
24 // k must be 1
25 return Math.max(A[0], B[0]);
26 }
27
28 int s = 0;
29 int e = A.length;
30
31 while ( s < e ){
32
33 int m = (s + e) / 2;
34
35 int n = k - m;
36
37 if ( A[m] <= safe(B, n) ) {
38 if (n == 0 || A[m] >= safe(B, n - 1)) {
39 return A[m];
40 }
41 }
42
43 if ( safe(B, n) <= A[m] ){
44 if (m == 0 || safe(B, n) >= A[m - 1]) {
45 return B[n];
46 }
47 }
48
49 if ( A[m] < safe(B, n) ) {
50 s = m + 1;
51 } else {
52 e = m;
53 }
54
55 }
56
57 if (A[A.length - 1] < B[0]){
58 return B[k - A.length];
59 } else {
60 return kth(B, A, k);
61 }
62
63 }
64
65
66 public double findMedianSortedArrays(int A[], int B[]) {
67 // median of {3, 3, 5, 9, 11} is 5
68 // the median of {3, 5, 7, 9} is (5 + 7) / 2 = 6 wikipedia
69
70 int s = A.length + B.length;
71 final int k = s / 2;
72
73 if(s % 2 == 1){
74 return kth(A, B, k);
75 }else{
76 return (kth(A, B, k - 1) + kth(A, B, k)) / 2.0;
77 }
78
79 }
80 }