【每日一题】中位数_一个在时间和空间两方面都尽可能高效的算法,找出两个序列的中位数

题目描述

---

一个长度为 L ( L ≥ 1 ) 的升序序列 S，处在第 [L / 2] 个位置的数称为 S 的中位数。
例如，若序列 S1 = (11, 13, 15, 17, 19)，则 S1 的中位数是 15 。
两个序列的中位数 是含它们所有元素的升序序列的中位数。例如，若 S2 = (2, 4, 6, 8, 20)，则 S1 和 S2 的中位数是 11 。
给出两个有序序列 A 和 B，它们的长度相等。
设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。

输入描述
第一行是 L，表示两个有序序列 A 和 B 的长度。1 < L ≤ 1000000
第二行是序列 A，空格分隔的 L 个整数。
第三行是序列 B，空格分隔的 L 个整数。
输出描述
一个整数，A 和 B 的中位数。

用例输入 1

5
11 13 15 17 19
2 4 6 8 20
1
2
3

用例输出 1

11
1

思路历程

---

思路1
一开始想将两组序列的数据都存储在一个容量为2*n的数组内，直接使用 sort 函数排序后输出中位数，无法AC ！！！

#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin>>n;
    int a[n*2+10];
    for(int i = 0;i<2*n;i++)
        cin>>a[i];

    sort(a,a+2*n);
    
    for(int i = 0 ; i<2*n;i++)
        cout<<a[i]<<" ";
        
    cout<<a[n -1]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 分析原因可能是 时间 超出限制
• 该思路本质上是把两个序列合并为一个序列后再排序，时间复杂度是 O((2n)log(2n))
• 同时，如果把两个序列合并为一个序列后再排序，代码也应该按照合并的方式进行实现，不应该把数据直接输入到一个数组中，这样会导致代码逻辑混乱，不易于维护。

思路2

根据中位数的定义，将问题转化为求两个有序序列中第 k 小的数，其中 k = (L+1)/2。可以使用二分查找的思想解决。

• 假设我们要找到两个有序序列 A 和 B 中第 k 小的数，我们可以分别取 A 和 B 的第 k/2 小的数 A[k/2-1] 和 B[k/2-1] 进行比较。
• 如果 A[k/2-1] < B[k/2-1]，那么 A[0] 到 A[k/2-1] 的所有数都不可能成为第 k 小的数，因此我们可以将这些数排除。排除后，问题转化为在剩余的 A[k/2:] 和 B 找到第 k-k/2 小的数。
• 反之，如果 A[k/2-1] > B[k/2-1]，那么 B[0] 到 B[k/2-1]的所有数都可以被排除。排除后，问题转化为在剩余的 A 和 B[k/2:] 中找到第 k-k/2 小的数。
• 如果 A[k/2-1] = B[k/2-1]，那么 A[k/2-1] 就是第 k 小的数。
• 注意边界条件的处理。如果 A 或 B 的长度小于 k/2，我们只需要取存在的那个序列的第 k/2 小的数即可。如果 A 和 B 的长度都小于 k/2，我们只需要取 A 和 B 中较大的那个数即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    
    int a[n], b[n];
    for (int i = 0; i < n; i++) 
        cin >> a[i];
    for (int i = 0; i < n; i++) 
        cin >> b[i];

    int i = 0,j =0, k = 0, mid = n - 1;
    while (i < n && j < n && k <= mid) 
    {
        if (a[i] < b[j]) 
        {
            if (k == mid) 
                cout << a[i] << endl;
            i++;
        } 
        else 
        {
            if (k == mid) cout << b[j] << endl;
            j++;
        }
        k++;
    }

    while (i < n && k <= mid) 
    {
        if (k == mid) 
            cout << a[i] << endl;
        i++,k++;
    }
    while (j < n && k <= mid)
    {
        if (k == mid) 
            cout << b[j] << endl;
        j++,k++;
    }

    return 0;
}
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
41
42
43
44
45
46
47
48
49

算法思路

• 定义三个指针 i、j 和 k，其中 i 和 j 分别指向两个有序数组中的元素，k 用于计数；
• 使用 while 循环依次比较 a[i] 和 b[j] 的大小，根据大小关系有如下两种情况：
• 如果 a[i] < b[j]，那么我们将 i++，表示在 a 中找到了一个比 b[j] 小的元素；
• 如果 a[i] >= b[j]，那么我们将 j++，表示在 b 中找到了一个比 a[i] 小的元素。
• 在每次比较中，当 k 的值已经达到中位数时，我们就可以输出当前的元素了；
• 如果其中一个数组已经遍历结束，即（i == n 或者 j == n），那么我们只需要在剩余的另一个数组中找到第 (m+n)/2-k 个元素即可。
• 时间复杂度为 O(log(min(m,n)))