4. Median of Two Sorted Arrays
2018-09-26 本文已影响0人
与你若只如初见v
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)).
You may assume nums1 and nums2 cannot be both empty.
Example 1
nums1 = [1, 3]
nums2 = [2]The median is 2.0
Example 2
nums1 = [1, 2]
nums2 = [3, 4]The median is (2 + 3)/2 = 2.5
Solution
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length,max = 0,min = 0;
if (nums1.length == 0) {
max = nums2[nums2.length-1];
min = nums2[0];
} else if (nums2.length == 0) {
max = nums1[nums1.length-1];
min = nums1[0];
} else {
max = nums1[nums1.length-1] > nums2[nums2.length-1] ? nums1[nums1.length-1] : nums2[nums2.length-1];
min = nums1[0] < nums2[0] ? nums1[0] : nums2[0];
}
int[] all = new int[max + 1 - min];
for (int i = 0; i < nums1.length; i++) {
all[nums1[i] - min]++;
}
for (int i = 0; i < nums2.length; i++) {
all[nums2[i] - min]++;
}
int index = len / 2 + 1;
int flag = len % 2;
int key = 0,tmp = -1;
for (int i = 0; i < max + 1 - min; i++) {
if (all[i] == 0) {
continue;
}
key += all[i];
if (flag == 1 && key >= index) {
return (double)(i + min);
}else if (flag == 0) {
if (tmp != -1 && all[i] != 0) {
return (i + tmp) / 2.0 + min;
}
if (key >= index) {
return (double)(i + min);
} else if (key == index - 1) {
tmp = i;
}
}
}
return 0.0;
}
}
强行用了一波桶排序。。。
