-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMedianOfTwoSortedArrays
More file actions
36 lines (33 loc) · 1.13 KB
/
MedianOfTwoSortedArrays
File metadata and controls
36 lines (33 loc) · 1.13 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
/*
There are two sorted arrays nums1 and nums2 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 Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int k = nums1.length + nums2.length;
if(k % 2 == 1){
return findKth(nums1 , nums2 , k / 2 + 1);
}else{
return (findKth(nums1 , nums2 , k / 2) + findKth(nums1 , nums2 , k / 2 + 1))/2;
}
}
public static double findKth(int[] nums1 , int[] nums2 , int k){
if(nums1.length > nums2.length){
return findKth(nums2 , nums1 , k);
}
if(nums1.length == 0){
return nums2[k - 1];
}
if(k <= 1){
return Math.min(nums1[0], nums2[0]);
}
int pa = Math.min(k / 2 , nums1.length) ;
int pb = k - pa;
if(nums1[pa - 1] < nums2[pb - 1]){
return findKth(Arrays.copyOfRange(nums1, pa , nums1.length) ,nums2 , k-pa );
}else if(nums1[pa - 1] > nums2[pb - 1]){
return findKth(nums1 , Arrays.copyOfRange(nums2 , pb , nums2.length) , k - pb);
}else{
return nums1[pa - 1];
}
}
}