一个长度为的升序序列，处在第个位置的数称为的中位数。例如，若序列，则_

[数据结构 P2089] 一个长度为的升序序列，处在第个位置的数称为的中位数。例如，若序列，则

学习人数: 32

正确率: ??%

题目描述

未通过

一个长度为 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 的中位数。要求：

⑴ 给出算法的基本设计思想。

⑵ 根据设计思想，采用C或C++或Java语言描述，关键之处给出注释。

⑶ 说明你所设计算法的时间复杂度和空间复杂度。

上一题

下一题

加入错题本

个人笔记

登录后提交答案

1 个回答 (点击展开回答)

hachi8mi

2024年10月29日 08:31

1.从小到大依次比较A和B中元素，比较L次后取更大的数作为中位数

2.int mid(int A[], int B[], int L){

int j=0,k=0;

for(int i=0;i<n;i++){

if(A[j]<B[k]) j++;

else k++;}

if(A[j]>B[k] return A[j];

else return B[k];

}

3.时间O(L) 空间O(1)

参考答案

两个有序数组分别是 A[...

用户登录可进行刷题及查看答案

两个有序数组分别是 A[0:n−1] 和 B[0:n−1] 。要找到第 n 个元素，我们可以比较 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 。

由于 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 的前面分别有 A[0:⌈n/2⌉−2] 和 B[0:⌈n/2⌉−2] ，即各有 ⌈n/2⌉−1 个元素，对于 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} ，

若 n 为奇数，则 2(⌈n/2⌉−1)<2(n/2+1−1)=n ，最多只会有 n−1 个元素比它小，也就是 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最多恰为第 n 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 A[0:⌈n/2⌉−2] （等价于 A[0:⌊n/2⌋−1] ）都小于或等于 A[⌈n/2⌉−1] ，可以直接排除。

若 n 为偶数，则 2(⌈n/2⌉−1)=2(n/2−1)=n−2 ，最多只会有 n−2 个元素比它小，也就是 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最多恰为第 n−1 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 A[0:⌈n/2⌉−1] （等价于 A[0:⌊n/2⌋−1] ）都小于或等于 A[⌈n/2⌉−1] ，可以直接排除。

由于 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 的后面分别有 A[⌈n/2⌉:n−1] 和 B[⌈n/2⌉:n−1] ，即各有 n−⌈n/2⌉ 个元素，对于 max{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} ，因为 2(n−⌈n/2⌉)≤2(n−n/2)=n 最多只会有 n 个元素比它大，也就是 max{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最少恰为第 n 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 B[⌈n/2⌉:n−1] （等价于 B[n−⌊n/2⌋−1:n−1] ）都大于或等于 B[⌈n/2⌉−1] ，可以直接排除。

因此我们可以归纳出三种情况：

情况一： A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，排除 A[0:⌊n/2⌋−1] 和 B[n−⌊n/2⌋−1:n−1] ，同时缩小 n 为 ⌈n/2⌉ 。
情况二： A[⌈n/2⌉−1]>B[⌈n/2⌉−1] ，排除 A[n−⌊n/2⌋−1:n−1] 和 B[0:⌊n/2⌋−1] ，同时缩小 n 为 ⌈n/2⌉ 。
情况三： A[⌈n/2⌉−1]=B[⌈n/2⌉−1] ，归纳为情况一或者情况二。

其实我们可以对情况三进行进一步讨论，此时设 A[⌈n/2⌉−1]=B[⌈n/2⌉−1]=m 。

若 n 为奇数，此时恰有 n−1 个元素小于或等于 m ，且恰有 n−1 个元素大于或等于 m ，取 A[⌈n/2⌉−1] 或 B[⌈n/2⌉−1] 放入大于或等于 m 的集合，则恰有 n−1 个元素小于或等于 m ，且恰有 n 个元素大于或等于 m ，则 m 为中位数，可以直接返回。

若 n 为偶数，此时恰有 n−2 个元素小于或等于 m ，且恰有 n−1 个元素大于或等于 m ，取 A[⌈n/2⌉−1] 或 B[⌈n/2⌉−1] 放入小于或等于 m 的集合，则恰有 n−1 个元素小于或等于 m ，且恰有 n 个元素大于或等于 m ，则 m 为中位数，可以直接返回。

因此三种情况可以优化为：

情况一： A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，排除 A[0:⌊n/2⌋−1] 和 B[n−⌊n/2⌋−1:n−1] ，同时缩小 n 为 ⌈n/2⌉ 。
情况二： A[⌈n/2⌉−1]>B[⌈n/2⌉−1] ，排除 A[n−⌊n/2⌋−1:n−1] 和 B[0:⌊n/2⌋−1] ，同时缩小 n 为 ⌈n/2⌉ 。
情况三： A[⌈n/2⌉−1]=B[⌈n/2⌉−1] ，直接返回 A[⌈n/2⌉−1] 。

递归调用上述过程，终止情况：

n=1 ，返回两个数组仅剩余两个元素中的最小值。

因为 0<⌈n/2⌉<n−1 ，所以不会越界。

画出有向图，→指向表示有向边，有向边起点元素小于或等于有向边终点元素。

如上图，灰色结点淘汰。

递归版本一，保存下标，为原地算法。这里总共有五个变量，两个数组的首尾元素下标合计4个，数组长度一个，由于 p+n−1=r ，我们只记录 A 首个元素下标 pa ，B 首个元素下标 pb ，和数组长度 n 。

C代码如下（含测试用例）：

#include <stdio.h>

int min(int x, int y) {
    return x < y ? x : y;
}

int findMedian(int *a, int *b, int n, int pa, int pb) {
    if (n == 1) {
        return min(a[pa], b[pb]);
    }
    int ma = pa + (n + 1) / 2 - 1;
    int mb = pb + (n + 1) / 2 - 1;
    if (a[ma] < b[mb]) {
        return findMedian(a, b, (n + 1) / 2, pa + n / 2, pb);
    } else if (a[ma] > b[mb]) {
        return findMedian(a, b, (n + 1) / 2, pa, pb + n / 2);
    } else {
        return a[ma];
    }
}

int findMedianSortedArrays(int *A, int *B, int n) {
    return findMedian(A, B, n, 0, 0);
}

int main() {
    int s1[] = {11, 13, 15, 17, 19};
    int s2[] = {2, 4, 6, 8, 20};
    printf("%d", findMedianSortedArrays(s1, s2, 5));
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int findMedian(vector<int>& A, vector<int>& B, int pa, int pb, int n) {
    if (n == 1) {
        return min(A[pa], B[pb]);
    }
    int ma = pa + (n + 1) / 2 - 1;
    int mb = pb + (n + 1) / 2 - 1;
    if (A[ma] < B[mb]) {
        return findMedian(A, B, pa + n / 2, pb, (n + 1) / 2);
    } else if (A[ma] > B[mb]) {
        return findMedian(A, B, pa, pb + n / 2, (n + 1) / 2);
    } else {
        return A[ma];
    }
}

int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    int n = (int)A.size();
    return findMedian(A, B, 0, 0, n);
}

int main() {
    vector<int>s1 = {11, 13, 15, 17, 19};
    vector<int>s2 = {2, 4, 6, 8, 20};
    cout << findMedianSortedArrays(s1, s2);
    return 0;
}

时间复杂度： O(log⁡n) 。
空间复杂度： O(1) 。

迭代版本一，保存下标，为原地算法。

C代码如下（含测试用例）：

#include <stdio.h>

int min(int x, int y) {
    return x < y ? x : y;
}

int findMedianSortedArrays(int *a, int *b, int n) {
    int pa = 0, pb = 0, ma, mb;
    while (n > 1) {
        ma = pa + (n + 1) / 2 - 1;
        mb = pb + (n + 1) / 2 - 1;
        if (a[ma] == b[mb]) return a[ma];
        if (a[ma] < b[mb]) {
            pa += n / 2;
        } else {
            pb += n / 2;
        }
        n = (n + 1) / 2;
    }
    return min(a[pa], b[pb]);
}

int main() {
    int s1[] = {11, 13, 15, 17, 19};
    int s2[] = {2, 4, 6, 8, 20};
    printf("%d", findMedianSortedArrays(s1, s2, 5));
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    int n = (int)A.size();
    int pa = 0, pb = 0, ma, mb;
    while (n > 1) {
        ma = pa + (n + 1) / 2 - 1;
        mb = pb + (n + 1) / 2 - 1;
        if (A[ma] == B[mb]) return A[ma];
        if (A[ma] < B[mb]) {
            pa += n / 2;
        } else {
            pb += n / 2;
        }
        n = (n + 1) / 2;
    }
    return min(A[pa], B[pb]);
}

int main() {
    vector<int>s1 = {11, 13, 15, 17, 19};
    vector<int>s2 = {2, 4, 6, 8, 20};
    cout << findMedianSortedArrays(s1, s2);
    return 0;
}

时间复杂度： O(log⁡n) 。
空间复杂度： O(1) 。

迭代版本二，C代码如下（含测试用例）：

#include <stdio.h>

int min(int x, int y) {
    return x < y ? x : y;
}

int findMedianSortedArrays(int *A, int *B, int n) { // n即为序列长度L
    int s1 = 0, e1 = n - 1, mid1, s2 = 0, e2 = n - 1, mid2;
    while(s1 != e1 || s2 != e2) {
        mid1 = (s1 + e1) / 2;
        mid2 = (s2 + e2) / 2;
        if (A[mid1] == B[mid2]) {
             return A[mid1];
        } else if (A[mid1] < B[mid2]) {
            // 分别考虑奇数和偶数，保持两个子数组元素个数相等
            if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
                 s1 = mid1;  // 舍弃A中间点以前的部分
                 e2 = mid2;  // 舍弃B中间点以后的部分
            } else { // 若元素个数为偶数
                 s1 = mid1 + 1;  // 舍弃A中间点及中间点以前的部分
                 e2 = mid2;  // 舍弃B中间点以后的部分
            }
        } else {
            // 分别考虑奇数和偶数，保持两个子数组元素个数相等
            if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
                 e1 = mid1;  // 舍弃A中间点以后的部分
                 s2 = mid2;  // 舍弃B中间点以前的部分
            } else { // 若元素个数为偶数
                 e1 = mid1;  // 舍弃A中间点以后的部分
                 s2 = mid2 + 1;  // 舍弃B中间点及中间点以前的部分
            }
        }
    }
    return min(A[s1], B[s2]);
}

int main() {
    int s1[] = {11, 13, 15, 17, 19};
    int s2[] = {2, 4, 6, 8, 20};
    printf("%d", findMedianSortedArrays(s1, s2, 5));
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    const int n = A.size();
    int s1 = 0, e1 = n - 1, mid1, s2 = 0, e2 = n - 1, mid2;
    while(s1 != e1 || s2 != e2) {
        mid1 = (s1 + e1) / 2;
        mid2 = (s2 + e2) / 2;
        if (A[mid1] == B[mid2]) {
             return A[mid1];
        } else if (A[mid1] < B[mid2]) {
            // 分别考虑奇数和偶数，保持两个子数组元素个数相等
            if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
                 s1 = mid1;  // 舍弃A中间点以前的部分
                 e2 = mid2;  // 舍弃B中间点以后的部分
            } else { // 若元素个数为偶数
                 s1 = mid1 + 1;  // 舍弃A中间点及中间点以前的部分
                 e2 = mid2;  // 舍弃B中间点以后的部分
            }
        } else {
            // 分别考虑奇数和偶数，保持两个子数组元素个数相等
            if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
                 e1 = mid1;  // 舍弃A中间点以后的部分
                 s2 = mid2;  // 舍弃B中间点以前的部分
            } else { // 若元素个数为偶数
                 e1 = mid1;  // 舍弃A中间点以后的部分
                 s2 = mid2 + 1;  // 舍弃B中间点及中间点以前的部分
            }
        }
    }
    return min(A[s1], B[s2]);
}

int main() {
    vector<int>s1 = {11, 13, 15, 17, 19};
    vector<int>s2 = {2, 4, 6, 8, 20};
    cout << findMedianSortedArrays(s1, s2);
    return 0;
}

时间复杂度： O(log⁡n) 。

空间复杂度： O(1) 。

[数据结构 P2089] 一个长度为 的升序序列 ，处在第 个位置的数称为 的中位数。例如，若序列 ，则

登录后提交答案

[数据结构 P2089] 一个长度为的升序序列，处在第个位置的数称为的中位数。例如，若序列，则