- Method1: Merge two sorted arrays to one and take the median of the arrayList.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums1.length == 0 && nums2.length != 0){
int size = nums2.length / 2;
if(nums2.length % 2 == 0){
return (nums2[size - 1] + nums2[size]) / 2.0d;
}else{
return nums2[size];
}
}
if(nums2.length == 0 && nums1.length != 0){
int size = nums1.length / 2;
if(nums1.length % 2 == 0){
return (nums1[size - 1] + nums1[size]) / 2.0d;
}else{
return nums1[size];
}
}
if(nums2.length == 0 && nums1.length == 0){
return 0.0d;
}
List<Integer> list = new ArrayList<>();
int index1 = 0;
int index2 = 0;
int complete = 0;
while(index1 < nums1.length && index2 < nums2.length){
if(nums1[index1] <= nums2[index2]){
list.add(new Integer(nums1[index1]));
index1++;
}else{
list.add(new Integer(nums2[index2]));
index2++;
}
if(index1 == nums1.length){
complete = 1;
}else if(index2 == nums2.length){
complete = 2;
}
}
if(complete == 1){
for(; index2 < nums2.length; index2++){
list.add(new Integer(nums2[index2]));
}
}else{
for(; index1 < nums1.length; index1++){
list.add(new Integer(nums1[index1]));
}
}
int size = list.size();
if(size % 2 == 0){
return (list.get(size/2 - 1) + list.get(size/2)) / 2.0d;
}else{
return list.get(size/2);
}
}
}- Method 1
- 使用merge将两个数组合并起来。
- 根据奇数或是偶数，返回中位数。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int first = 0, second = 0;
int[] merge = new int[len1 + len2];
int count = 0;
while(first < len1 || second < len2){
if(first < len1 && second < len2)
merge[count++] = nums1[first] <= nums2[second] ? nums1[first++]: nums2[second++];
else if(first < len1)
merge[count++] = nums1[first++];
else
merge[count++] = nums2[second++];
}
return (len1 + len2) % 2 != 0 ?
(double)merge[(len1 + len2) / 2] :
((double)merge[(len1 + len2) / 2] + (double)merge[(len1 + len2) / 2 - 1]) / 2;
}
}- Method 2
- 将两个数组合并起来，再排序。
- 根据奇数偶数来去除中位数。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] merge = new int[nums1.length + nums2.length];
int i = 0;
for(i = 0; i < nums1.length; i++)
merge[i] = nums1[i];
for(; i - nums1.length < nums2.length; i++)
merge[i] = nums2[i - nums1.length];
Arrays.sort(merge);
return (merge.length) % 2 != 0 ?
(double)merge[merge.length / 2] : (double)(merge[merge.length / 2] + merge[merge.length / 2 - 1]) / 2;
}
}- Method 1: binary search
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; if(m > n) return findMedianSortedArrays(nums2, nums1); int k = (m + n + 1) / 2; int left = 0, right = m; while(left < right){ int mid1 = left + (right - left) / 2; int mid2 = k - mid1; if(nums1[mid1] < nums2[mid2 - 1]) left = mid1 + 1; else right = mid1; } int mid1 = left; int mid2 = k - left; int c1 = Math.max(mid1 <= 0 ? Integer.MIN_VALUE: nums1[mid1 - 1], mid2 <= 0 ? Integer.MIN_VALUE: nums2[mid2 - 1]); if((m + n) % 2 != 0) return (double)c1; int c2 = Math.min(mid1 >= m ? Integer.MAX_VALUE: nums1[mid1], mid2 >= n ? Integer.MAX_VALUE: nums2[mid2]); return (c1 + c2) * 0.5; } }
-
Method 1: Merge and find medium
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] arr = new int[nums1.length + nums2.length]; int index1 = 0, index2 = 0, index = 0; while(index1 < nums1.length && index2 < nums2.length){ if(nums1[index1] <= nums2[index2]){ arr[index++] = nums1[index1++]; }else{ arr[index++] = nums2[index2++]; } } if(index1 == nums1.length){ // nums1 reached the end, need to append nums2 for(; index < nums1.length + nums2.length; index++){ arr[index] = nums2[index2++]; } }else{ for(; index < nums1.length + nums2.length; index++){ arr[index] = nums1[index1++]; } } return arr.length % 2 == 1 ? (double)arr[arr.length/2]: (double)(arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2; } }
-
Method 2: Binary search
- Medium value is created by C1 and C2.
- There are totally K = (len1 + len2 + 1) / 2 will be selected to create the left side of the merged array.
- We use m1 numbers from nums1 and m2 values from nums2, k = m1 + m2.
- The constraint for binary search is nums1[m1 - 1] <= nums2[m2 - 1].
- If total number of values are even, result is (Ck + Ck-1) / 2 else Ck-1.
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1 = nums1.length, len2 = nums2.length; if(len2 < len1) return findMedianSortedArrays(nums2, nums1); int k = (len1 + len2 + 1) / 2; int l = 0, r = len1, m1 = 0; while(l < r){ m1 = l + (r - l) / 2; int m2 = k - m1; if(nums1[m1] < nums2[m2 - 1]) l = m1 + 1; else r = m1; } m1 = l; int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE: nums1[m1 - 1], k - m1 <= 0 ? Integer.MIN_VALUE: nums2[k - m1 - 1]); if((len1 + len2) % 2 == 1) return (double)c1; int c2 = Math.min(m1 >= len1 ? Integer.MAX_VALUE: nums1[m1], k - m1 >= len2 ? Integer.MAX_VALUE: nums2[k - m1]); return (double)(c1 + c2) / 2; } }
