-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathMedianSorted.java
More file actions
110 lines (94 loc) · 2.82 KB
/
MedianSorted.java
File metadata and controls
110 lines (94 loc) · 2.82 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package collection3;
/*
* 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)).
*/
public class MedianSorted {
public static double findMedianSortedArrays(int A[], int B[]) {
if(A==null &&B==null) return 0.0;
if(A==null){
if(B.length%2==0){
return ((double)B[B.length/2-1]+(double)B[B.length/2])/2;
} else {
return (double)B[B.length/2];
}
}
if(B==null){
if(A.length%2==0){
return ((double)A[A.length/2-1]+(double)A[A.length/2])/2;
} else {
return (double)A[A.length/2];
}
}
if(A[A.length-1]<B[0]){
if(A.length<B.length){
if((A.length+B.length)%2 ==0){
return ((double)B[(A.length+B.length)/2-1-A.length]+(double)B[(A.length+B.length)/2-A.length])/2;
} else {
return (double)B[(A.length+B.length)/2-A.length];
}
} else if(A.length == B.length){
return ((double)A[A.length-1]+(double)B[0])/2;
} else {
if((A.length+B.length)%2 ==0){
return ((double)A[(A.length+B.length)/2-1]+(double)A[(A.length+B.length)/2])/2;
} else {
return (double)A[(A.length+B.length)/2];
}
}
}
if(B[B.length-1]<A[0]){
if(B.length<A.length){
if((A.length+B.length)%2 ==0){
return ((double)A[(A.length+B.length)/2-1-A.length]+(double)A[(A.length+B.length)/2-A.length])/2;
} else {
return (double)A[(A.length+B.length)/2-A.length];
}
} else if(A.length == B.length){
return ((double)B[B.length-1]+(double)A[0])/2;
} else {
if((A.length+B.length)%2 ==0){
return ((double)B[(A.length+B.length)/2-1]+(double)B[(A.length+B.length)/2])/2;
} else {
return (double)B[(A.length+B.length)/2];
}
}
}
return -1.0;
//if(A[A.length-1]>B[0]&&A.length>=B.length) return A[]
//return findk(A, B,);
}
public static double findk(int A[], int B[], int pos){
//pos-1;
int valuea = A[(A.length-1)/2];
int posb = pos-1-(A.length-1)/2;
if(valuea>B[posb-1]&&valuea<B[posb]){
return (double)valuea;
} else if(valuea<B[posb-1]){
} else if(valuea>B[posb]){
}
return 0.0;
}
public static int findone(int A[], int start, int end, int pos){
return A[start+pos];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//test 1: A= null, B = null
System.out.println(findMedianSortedArrays(null,null));
//test 2: A[1,2,3], B = null
int[] a = {1,2,3};
System.out.println(findMedianSortedArrays(a,null));
//test 3: A null, B [2,4,5,7]
int[] b = {2,4,5,7};
System.out.println(findMedianSortedArrays(null,b));
//test 4: A [1,2,3] B[5,7,9]
int[] c={5,7,9};
System.out.println(findMedianSortedArrays(a,c));
//test 5: d[5,6,7] e[1,2,3,4]
int[] d = {5,6,7};
int[] e = {1,2,3,4};
System.out.println(findMedianSortedArrays(d,e));
}
}