1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length == 0 && nums2.length == 0) {
return 0.0;
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
for (int i = 0; i < nums1.length; i++) {
addNum(nums1[i], minHeap, maxHeap);
}
for (int i = 0; i < nums2.length; i++) {
addNum(nums2[i], minHeap, maxHeap);
}
return minHeap.size() == maxHeap.size() ? (minHeap.peek() + maxHeap.peek()) * 0.5 : (double) minHeap.peek();
}
private void addNum(int num, PriorityQueue<Integer> minHeap, PriorityQueue<Integer> maxHeap) {
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
if (maxHeap.size() > minHeap.size()) {
minHeap.offer(maxHeap.poll());
}
}
}
|
Two heaps. 当练手了.
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
| class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int left = 0, right = nums1.length, firstHalfLength = (nums1.length + nums2.length + 1) / 2;
double ans = 0;
while (left <= right) {
int partitionX = left + (right - left) / 2, partitionY = firstHalfLength - partitionX;
int maxLeftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX - 1];
int minRightX = partitionX == nums1.length ? Integer.MAX_VALUE : nums1[partitionX];
int maxLeftY = partitionY == 0 ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minRightY = partitionY == nums2.length ? Integer.MAX_VALUE : nums2[partitionY];
if (maxLeftX > minRightY) {
right = partitionX - 1;
} else if (maxLeftY > minRightX) {
left = partitionX + 1;
} else {
if ((nums1.length + nums2.length) % 2 == 0) {
ans = 0.5 * (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY));
} else {
ans = (double) Math.max(maxLeftX, maxLeftY);
}
break;
}
}
return ans;
}
}
|
这才是正规解法.
大致的思路就是我们要把nums1和nums2都划分成两部分, 这样nums1前半部分和nums2前半部分加起来是二者总长度的一半. 如果总长度是奇数个, 那么我们让nums1和nums2前一半是二者长度一半 + 1. 这也就是第六行为什么让firstHalfLength等于二者长度 + 1除以2了, 因为即使二者长度是偶数, 我们也是保证nums1前一半 + nums2前一半是二者总长度的一半.
此时的问题就是如何划分, 这就到binary search登场了. 我们由于知道nums1和nums2前一半加在一起是个定值, 那么我们就先划分nums1, 之后nums2的划分也就自然确定下来了. 那么如何知道我们划分好了呢? 我们要保证nums1前一半的最后一个元素要小于nums2后一半第一个元素, 同样地, nums2的前一半的最后一个元素要小于nums1后一半的第一个元素. 这样我们就能保证nums1和nums2各自的前一半组成的部分就是nums1和nums2 merge后的前一半.
此时如果nums1.length + nums2.length是奇数. 那么我们就看nums1和nums2前一半最后一个数字哪个大, 大的那个就是median; 如果是偶数, 那就要看nums1和nums2前一半的最后一个数哪个大, nums1和nums2的后一半第一个数哪个小, 得出的这两个结果求平均值就是答案.
此时有个问题, 如果nums1或者nums2没有前一半, 也就是可能nums1的数字都贼大, 前一半都在nums2里面, 反之类似地道理. 或者nums1没有后一半, 那也就是nums1的数字都用上来贡献了.
因此这两种情况我们需要考虑. 上面的left和right表示可以用来分割的点有哪些, 取mid后表示mid左边是被包含进nums1前一半的元素, 此时注意是不包含mid这个元素的. 因为我们如果要包含进所有的划分方式, 必须考虑到一个也不包含的情况. 那么如果我们规定mid是被包含进划分的partition中的, 这个一个也不包含的情况就会被遗漏. 因此left和right框起来的区域表示nums1后一半可以开始的地方.
于是当我们发现paritionX是0的时候, 这表示, nums1前一半没东西, 那么根据我们上面的逻辑, 我们可能要取nums1前一半和nums2前一半的最大值, 而此时我们nums1没东西, 那我们希望的就是取nums2的前一半的最大值即可, 于是我们手动让nums1前一半最小值设置为Integer.MAX_VALUE. 如果partitionX是nums1.length, 那说明nums1全部取走了, 此时nums1没有后一半, 根据我们上面的逻辑, 我们可能要取nums1和nums2后一半的最小值, 此时那就是直接取nums2后一半的最小值即可. 那么我们为了满足这个逻辑, 让nums1后一半的最小值是Integer.MIN_VALUE即可, 这样到时候比较的时候就会取nums2的后一半第一个元素.
对于nums2的操作是一样的, 判断它有没有前一半后一半, 这里就不再赘述.
时间复杂度: O(log(m + n))
空间复杂度: O(1)
