forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMedianofTwoSortedArrays.java
More file actions
49 lines (46 loc) · 1.87 KB
/
MedianofTwoSortedArrays.java
File metadata and controls
49 lines (46 loc) · 1.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
Author: King, wangjingui@outlook.com
Date: Dec 12, 2014
Problem: Median of Two Sorted Arrays
Difficulty: Hard
Source: http://leetcode.com/onlinejudge#question_4
Notes:
There are two sorted arrays A and B of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Solution: 1. O(m+n)
2. O(log(m+n))
*/
public class Solution {
public double findMedianSortedArrays_1(int A[], int B[]) {
int m = A.length, n = B.length;
int total = n + m, m1=0, m2=0, i=0, j=0;
for (int k = 1; k <= total/2 + 1; ++k) {
int a = (i==m) ? Integer.MAX_VALUE : A[i];
int b = (j==n) ? Integer.MAX_VALUE : B[j];
m1 = m2;
m2 = Math.min(a,b);
if (a > b) ++j;
else ++i;
}
if ((total&1) == 1) return m2;
else return (m1+m2)/2.0;
}
public double findMedianSortedArrays_2(int A[], int B[]) {
int m = A.length, n = B.length;
int total = m + n;
int k = total / 2;
if ((total&1) == 1) return findKth(A,B,k+1,0,m-1,0,n-1);
else return (findKth(A,B,k,0,m-1,0,n-1)+findKth(A,B,k+1,0,m-1,0,n-1))/2.0;
}
public double findKth(int A[], int B[], int k, int astart, int aend, int bstart, int bend) {
int alen = aend - astart + 1;
int blen = bend - bstart + 1;
if (alen > blen) return findKth(B,A,k, bstart, bend, astart, aend);
if (alen == 0) return B[bstart + k - 1];
if (k == 1) return Math.min(A[astart],B[bstart]);
int sa = Math.min(alen, k/2), sb = k- sa;
if (A[astart+sa-1] == B[bstart+sb-1]) return A[astart+sa-1];
else if (A[astart+sa-1] > B[bstart+sb-1]) return findKth(A,B,k - sb,astart,aend,bstart+sb,bend);
else return findKth(A,B,k - sa,astart+sa,aend,bstart,bend);
}
}