Keshawn_lu's Blog

Leetcode 4. 寻找两个正序数组的中位数

字数统计: 1.3k阅读时长: 5 min
2020/05/24 Share

题目简介:

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1nums2

请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1nums2 不会同时为空。

示例 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

思路:

由于要求时间复杂度为O(log(m + n)),所以就不能粗暴的将两个数组直接合并再排序了。而是要用到二分的思想,看了大佬们的题解后,找到了一种还算是能理解的算法,相当于把这个问题转化成了找第 K 小的元素。

假设我们要找第 k 小数,我们可以每次循环排除掉 k/2 个数。看下边一个例子。

假设我们要找第 7 小的数字。(4 + 10) / 2 = 7

我们比较两个数组的第 k/2 个数字,如果 k 是奇数,向下取整。也就是比较第 3 个数字

因为 3 < 4,所以第二个数组的1,2,3都可以排除掉,相当于排除了3个数字。

由于我们已经排除掉了 3 个数字,就是这 3 个数字一定在最前边,所以在两个新数组中,我们只需要找第 7 - 3 = 4 小的数字就可以了,也就是 k = 4。

橙色的部分表示已经去掉的数字。

此时两个数组,比较第 2 个数字,3 < 5,所以我们可以把小的那个数组中的 1 ,3 排除掉了。

我们又排除掉 2 个数字,所以现在找第 4 - 2 = 2 小的数字就可以了。此时比较两个数组中的第 k / 2 = 1 个数

此时我们要比较第 1 个数字,判断两个数组中第一个数字哪个小就可以了,虽然此时两个数相等,但是我们无论去掉哪个数组中的都行,因为去掉 1 个总会保留 1 个的,所以没有影响。

由于又去掉 1 个数字,此时我们要找第 1 小的数字,所以只需判断两个数组中第一个数字哪个小就可以了,也就是 4。

所以第 7 小的数字是 4。

我们每次都是取 k/2 的数进行比较,有时候可能会遇到数组长度小于 k/2的时候。

此时 k / 2 等于 3,而上边的数组长度是 2,我们此时将箭头指向它的末尾就可以了。这样的话,由于 2 < 3,所以就会导致上边的数组 1,2 都被排除。造成下边的情况。

由于 2 个元素被排除,所以此时 k = 5,又由于上边的数组已经空了,我们只需要返回下边的数组的第 5 个数字就可以了。

讲完例子,回到代码中,关键点就是两个数组每次是否能找到第 K / 2 个数字,如果找到了就把该值取出来,找不到就赋上一个INT_MAX,然后比较两个数组第 K/2个数字,哪个数组的第 k/2个数字小,就把该数组的前k/2个数字都排除掉,并将该数组的起始位置往后移动k/2个位置,并且k需要减去k/2,递归即可。

由于两个数组长度之和 m+n 的奇偶不确定,因此需要分情况来讨论,对于奇数的情况,直接找到最中间的数即可,偶数的话需要求最中间两个数的平均值。我们分别找第 (m+n+1) / 2 个,和 (m+n+2) / 2 个,然后求其平均值即可,这对奇偶数均适用。假如 m+n 为奇数的话,那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等,相当于两个相同的数字相加再除以2,还是其本身。

tips:

  • 若数组的起始位置大于等于该数组的长度,说明该数组已经排除了所有元素,已为空。

  • k == 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
33
34
35
36
37
38
39
40
class Solution {
public:

//寻找第K小的元素
int findKth(vector<int> nums1, int start1, vector<int> nums2, int start2, int k){

if(start1 >= nums1.size()) //nums1已经删除了全部元素,已为空
return nums2[start2 + k - 1];
if(start2 >= nums2.size()) //nums2已经删除了全部元素,已为空
return nums1[start1 + k - 1];

if(k == 1)
return min(nums1[start1], nums2[start2]);

//判断两个数组是否存在第 k/2 个数字
int mid_nums1 = (start1 + k / 2 - 1 < nums1.size())
? nums1[start1 + k / 2 - 1] : INT_MAX;

int mid_nums2 = (start2 + k / 2 - 1 < nums2.size())
? nums2[start2 + k / 2 - 1] : INT_MAX;

//删除了 k/2 个数字
if(mid_nums1 < mid_nums2)
return findKth(nums1, start1 + k / 2, nums2, start2, k - k / 2);
else
return findKth(nums1, start1, nums2, start2 + k / 2, k - k / 2);
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

int m = nums1.size();
int n = nums2.size();

int k1 = (m + n + 1) / 2;
int k2 = (m + n + 2) / 2;

return (findKth(nums1, 0, nums2, 0, k1) + findKth(nums1, 0, nums2, 0, k2)) / 2.0;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: