【每日算法Day 71】寻找两个正序数组的中位数
Wallace Xu 2020-08-10 二分查找
这是一道很经典的利用有序性质进行二分查找的题目，其缩小搜索空间的逻辑很值得推敲。
# LeetCode 4. 寻找两个正序数组的中位数 (opens new window)
# 题目描述
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
# 示例
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
1
2
3
4
2
3
4
# 解题思路
本题和剑指上的“数据流的中位数”有些类似，可能很快想到用两个容量大小不超过1的堆来完成：
public class No4_MedianOfTwoSortedArrays {
PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>((a, b) -> b - a);
int total = insertToHeap(nums2, insertToHeap(nums1, 0));
return (total & 1) == 1 ? minHeap.peek() : (minHeap.peek() + maxHeap.peek()) / 2.0;
}
private int insertToHeap(int[] nums, int count) {
if (nums != null) {
for (int num : nums) {
count++;
if ((count & 1) == 1) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
} else {
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
}
}
}
return count;
}
}
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
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
虽然这种方法提交也勉强通过了，但是没有利用到两个数组都是已排序的性质，时间复杂度为O((m+n)log(m+n))，还用了额外的O(m+n)空间，没有达到题目要求的O(log(m + n))的时间复杂度。
这里求中位数可以一般化为在两个正序排序数组中找第K位的数。我们考虑数组A的前k/2个数和B的前k/2个数，假设A的第k/2个数小于B的第k/2个数，则就算B的前k/2个数中剩下的数都小于A的第k/2个数，A的第k/2个数也最多只可能是合并数组的第K-1个数，所以该数及前面的所有数就可以排除了。此时K-=排除掉的个数，对两个数组剩余的部分继续进行搜索，直到k==1。
AB反之亦然，如果AB的第k/2个数相同，任取一个就可以了，剩下的一个数在下次比较时就能确定；如果有数组的搜索范围已经为空，则找到另一个数组剩余搜索范围中的第k个元素即可。
class BS_MedianOfTwoSortedArrays {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null) return singleArray(nums2);
if (nums2 == null) return singleArray(nums1);
int len1 = nums1.length, len2 = nums2.length;
int leftMedian = (len1 + len2 + 1) / 2, rightMedian = (len1 + len2 + 2) / 2;
return 0.5 * (getKthNum(nums1, 0, len1 - 1, nums2, 0, len2 - 1, leftMedian) +
getKthNum(nums1, 0, len1 - 1, nums2, 0, len2 - 1, rightMedian));
}
private double singleArray(int[] array) {
int len = array.length;
if ((len & 1) == 1)
return array[len / 2];
else
return (array[len / 2] + array[len / 2 - 1]) / 2.0;
}
private int getKthNum(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int range1 = end1 - start1 + 1, range2 = end2 - start2 + 1;
//保证nums1一定是搜索范围更小的那个
if (range1 > range2) return getKthNum(nums2, start2, end2, nums1, start1, end1, k);
if (range1 == 0) return nums2[start2 + k - 1];
if (k == 1) return Math.min(nums1[start1], nums2[start2]);
int last1 = start1 + Math.min(range1, k / 2) - 1, last2 = start2 + Math.min(range2, k / 2) - 1;
if (nums1[last1] < nums2[last2])
return getKthNum(nums1, last1 + 1, end1, nums2, start2, end2, k - (last1 - start1 + 1));
else
return getKthNum(nums1, start1, end1, nums2, last2 + 1, end2, k - (last2 - start2 + 1));
}
}
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
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
每进行一次搜索，我们就减少 k/2 个元素，所以时间复杂度是 O(logk)，而 k=(m+n)/2，所以最终的复杂也就是O(log(m+n))。