寻找中位数

寻找中位数

中位数概念

一组有序数列中,居于中间位置的那个数,代表一个样本或概率分布的一个数值。譬如[1, 2, 3, 4, 5]的中位数为3,[1, 2, 3, 4, 5, 6]这个数列中居于中间的数字有两个34,那么中位数应该是3.5(3和4的平均值).

题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

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

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0
示例 2:

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

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

暴力解决

采用类似归并排序的思想,从两个有序数列的最小值开始进行比较排序,一直排到中位数附近。
需考虑特殊情况:

  1. m + n的和为基数还是偶数;
  2. 其中一个数列为空;
  3. 其中一个数列先排完;

时间复杂度为O(m + n),空间复杂度为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int left = 0, right = 0;
int start1 = 0, start2 = 0;
int size = nums1Size + nums2Size;

for (int i = 0; i <= size/2; i++) {
left = right;
if (start1 < nums1Size && (start2 >= nums2Size || nums1[start1] < nums2[start2])) {
right = nums1[start1++];
} else {
right = nums2[start2++];
}
}

if ((size & 1) == 0) {
return (left + right)/2.0;
}
return right;
}

时间复杂度为O(m + n),空间复杂度为O(1)

二分查找

二分法查找第n大的数

  1. 对于一个有序数组来说,其中位数始终可以用mid = (nums((n + 1)/2) + nums((n + 2)))/2的公式求出
  2. 那么对于两个有序数组来说,我们只要找出两个数组集合中第(m+n+1)/2大的数和第(m+n+2)/2大的数,然后求平均数即可。注意这里的第(m+n+1)/2大的数中m和n分别指两个数组的大小;
  3. 所以对于本题,也就转换为了找出两个数组集合中第k大的数,而我们采用类似二分查找的方法来找到这个数。

首先来看看对于两个数组
nums1: [a1, a2, ..., a(k/2), ...]
nums2: [b1, b2, ..., b(k/2), ...]

如果a(k/2) < b(k/2), 考虑两种极端情况:

  1. b(k/2)前所有的数b1, ... b(k/2-1)都大于a(k/2),也就是说比a(k/2)小的数只有a(k/2)之前的数,也就是a1, ..., a(k/2-1), 那么a(k/2)也就是nums1nums2两个数组中第k/2大的数;
  2. b(k/2)前所有的数b1, ... b(k/2-1)都小于a(k/2),也就是说比a(k/2)小的数只有a(k/2)之前的数(a1, ..., a(k/2-1))和b(k/2)之前的数(b1, ... b(k/2-1)),那么a(k/2)也就是nums1nums2两个数组中第k/2-1 + k/2-1 + 1= k-1大的数;

所以,在a(k/2) < b(k/2)这个条件下,a(k/2)在两个数组中最小是第k/2大的数,最大是k-1大的数,也就是第k大的数永远不可能在nums1中a(k/2)之前的数中产生,那么我们把a1, ..., a(k/2-1)丢弃掉,在剩余的数中继续找第k-(k/2-1)=k/2+1(代码实现中为k-k/2=k/2是因为代码中为下标运算),一直递归下去一直到当k=1或者其中一个数组长度为0`了,然后结束。

  1. k = 1, 即找两个数组中第1大的数,那么只需比较两个有序数组的起始元素;
  2. 当其中一个数据长度为0了,只需去另一个数组中找到第k大的数即可;
  3. 我们每次都是取k/2的数进行比较,有时候可能会遇到数组长度小于k/2的时候,即nums1: [a1, a2] 2 < k/2, num2: [b1, ..., b(k/2), ...],这时候只需要舍弃另一个数组中k/2前的数即b1, ..., b(k/2-1)就行了(2 < k/2, k/2-1 + 2 < k/2-1 + k/2 = 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
#include <limits.h>
// 在两个有序数组中二分查找第k大元素
int getKth(int* nums1, int nums1Size, int start1, int* nums2, int nums2Size, int start2, int k) {
if(start1 > nums1Size-1) return nums2[start2 + k - 1];
if(start2 > nums2Size-1) return nums1[start1 + k - 1];
// 当k等于1即在两个数组中找最小的元素,即只用比较两个有序数组的起始元素
if(k == 1) return nums1[start1] < nums2[start2] ? nums1[start1] : nums2[start2];

// 分别在两个数组中查找第k/2个元素,若存在(即数组没有越界),标记为找到的值;若不存在,标记为整数最大值
int nums1Mid = start1 + k/2 - 1 < nums1Size ? nums1[start1 + k/2 - 1] : INT_MAX;
int nums2Mid = start2 + k/2 - 1 < nums2Size ? nums2[start2 + k/2 - 1] : INT_MAX;

// 确定最终的第k/2个元素,然后递归查找
if(nums1Mid < nums2Mid)
return getKth(nums1, nums1Size, start1 + k/2, nums2, nums2Size, start2, k-k/2);
else
return getKth(nums1, nums1Size, start1, nums2, nums2Size, start2 + k/2, k-k/2);
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int l = (nums1Size + nums2Size + 1) / 2;
int r = (nums1Size + nums2Size + 2) / 2;
int value1 = getKth(nums1, nums1Size, 0, nums2, nums2Size, 0, l);
int value2 = getKth(nums1, nums1Size, 0, nums2, nums2Size, 0, r);
return (value1 + value2) / 2.0;
}

时间复杂度:每进行一次循环,我们就减少 k/2 个元素,所以时间复杂度是 O(log(k),而 k=(m+n)/2,所以最终的复杂也就是 O(log(m+n)。
空间复杂度为O(1)。

二分法切割

让我们在上一个算法的基础上再看看。
nums1: [a1, a2, ..., a(k/2), a(k/2+1), ..., a(m)]
nums2: [b1, b2, ..., b(k/2), b(k/2+1), ..., b(n)]

如果a[k/2] <= b[k/2]并且b[k/2] <= a[k/2],也就是意味着[a1, ..., a(k/2), b1, …, b(k/2)]中的数始终不可能比[a(k/2+1), …, a(m), b(k/2), …, b(n)]中的数大,那么第k大的数则为a(k/2)`、b(k/2)中比较大的那一个。

那么在本题中,我们要找的是第(m+n+1)/2大的数,来来来,转换一下,假设我们对num1进行切割,切割点为i,对nums2的切割点为(m+n+1)/2-i
nums1: [a1, a2, ..., a(i), a(i+1), ..., a(m)]
nums2: [b1, b2, ..., b((m+n+1)/2-i), b((m+n+1)/2-i+1), ..., b(n)]

  • a(i) < b((m+n+1)/2-i+1)并且b((m+n+1)/2-i) < a(i+1)时,中位数为max(a(i), b((m+n+1)/2-i)(m+n为奇数),或者(max(a(i), b((m+n+1)/2-i)) + min(a(i+1), b((n+1)/2-i+1)))/2(m+n为偶数)
  • 所以我们只需要在nums1数组中找出一个切割点i,使得a(i) < b((m+n+1)/2-i+1)并且b((m+n+1)/2-i) < a(i+1),就可以找到我们所需要的中位数
  • 那么怎么样从nums1中找到这个切割点呢,我们这里采用二分法来进行切割,首先让i=m/2, 如果a(i) > b((m+n+1)/2-i+1),则从a(i)的左边进行二分切割,如果a(i+1) < b((m+n+1)/2-i),则从a(i)的左边进行二分切割,一直切割到满足条件为止;

当然这里面要考虑到特殊情况,如果切割点到头了怎么办,也就是:

  1. i = 0时,说明nums1中所有数都大于中位数,则中位数为b((m+n+1)/2-m0(m+n为奇数), 或(b((m+n+1)/2-0) + min(a1 , b((m+n+1)/2-0+1)))/2.0(m+n为偶数数);
  2. i = m时,说明nums1中所有数都小于总位数,则中位数为min(am, b((m+n+1)/2-m))(m+n为奇数),或(min(am, b((m+n+1)/2-m)) + b((m+n+1)/2-m+1))/2.0 (m+n为偶数数)
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
#include <stdio.h>
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
if (nums1Size > nums2Size) {
return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
}

int maxLeft = 0, minRight = 0;
int min = 0, max =nums1Size;

while (min <= max){
int cut1 = (min + max)/2;
int cut2 = (nums1Size + nums2Size + 1)/2 - cut1;

int LMax1 = (cut1 == 0) ? INT_MIN : nums1[cut1-1];
int RMin1 = (cut1 == nums1Size) ? INT_MAX : nums1[cut1];
int LMax2 = (cut2 == 0) ? INT_MIN : nums2[cut2 - 1];
int RMin2 = (cut2 == nums2Size) ? INT_MAX : nums2[cut2];

if (cut1 > min && LMax1 > RMin2) {
max = cut1 - 1;
} else if (cut1 < max && LMax2 > RMin1) {
min = cut1 + 1;
} else {
maxLeft = max(LMax1, LMax2);
minRight = min(RMin1, RMin2);
break;
}
}

if (((nums1Size + nums2Size) & 1) == 0) {
return (maxLeft + minRight) / 2.0;
} else {
return maxLeft;
}
}