寻找中位数

发表于 | 分类于 ， | 评论： | 阅读次数：

寻找中位数

中位数概念

一组有序数列中，居于中间位置的那个数，代表一个样本或概率分布的一个数值。譬如[1, 2, 3, 4, 5]的中位数为3，[1, 2, 3, 4, 5, 6]这个数列中居于中间的数字有两个3和4，那么中位数应该是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)也就是nums1和nums2两个数组中第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)也就是nums1和nums2两个数组中第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;
    }
}