两个升序序列的中位数的代码

以下是Python代码实现：

def findMedianSortedArrays(nums1, nums2):
    # 合并两个有序数组
    nums = nums1 + nums2
    nums.sort()
    n = len(nums)
    # 根据数组长度的奇偶性来确定中位数的位置
    if n % 2 == 0:
        return (nums[n//2-1] + nums[n//2]) / 2
    else:
        return nums[n//2]

代码思路：

1. 将两个有序数组合并成一个有序数组；
2. 根据数组长度的奇偶性来确定中位数的位置，分别计算中位数。

时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别为两个数组的长度。因为需要进行一次合并和排序操作。

空间复杂度：$O(m+n)$，因为需要创建一个新的数组来存储合并后的有序数组。

相关问题

现在有两个等长升序序列 A和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求: 1) 给出算法的基本设计思想。

算法的基本设计思想是利用二分查找的思想，通过比较A和B序列的中位数及其左右两侧的数值关系，来缩小中位数的范围，最终找到中位数。

具体实现步骤如下：

1. 取A和B序列的中位数位置mid，分别为A[mid]和B[mid]；
2. 比较A[mid]和B[mid]的大小，如果A[mid]<B[mid]，则中位数必定在A[mid:]和B[:mid+1]之间，将A序列的左半部分和B序列的右半部分舍去，进而在A[mid+1:]和B[:mid+1]中查找中位数；
3. 如果A[mid]>B[mid]，则中位数必定在A[:mid+1]和B[mid:]之间，将A序列的右半部分和B序列的左半部分舍去，进而在A[:mid+1]和B[mid+1:]中查找中位数；
4. 如果A[mid]=B[mid]，则中位数为A[mid]或B[mid]；
5. 重复执行步骤2-4，直到找到中位数。

通过二分查找的思想，每次都可以将查找范围缩小一半，因此时间复杂度为O(logn)，空间复杂度为O(1)。

C语言编程题 2. 求两个等长有序序列的中位数 【问题描述】请按照如下的算法思想，利用折半查找方法求解两个升序序列A\B的中位数。（中位数的定义见教材P69 2.17） 算法思想：分别求出A，B的中位数a，b。若a=b,则a或者b就是所求；否则，舍弃a，b中较小者所在序列之较小一半，同时，舍弃较大者所在序列之较大的一半，且要求两次舍弃的元素个数相同。在保留的两个升序序列里重复这个过程，直到两个序列均只含有一个元素为止，此时，较小者即为所求。 提示：定义search(Rectype A[],Rectype B[],int n); 函数求出A、B的中位数。 测试数据用例Rectype 为int。 【输入形式】 从键盘输入一个整数表示表长-> 输入升序序列A和B->依次输出A、B舍弃部分元素后的序列->输出中位数 【输出形式】 每次A、B舍弃部分元素之后的序列 最终的中位数 【样例输入】 6 1 3 5 7 9 11 10 12 14 16 18 19 【样例输出】 7 9 11 10 12 14 9 11 10 12 11 10 mid=10

以下是求解两个等长有序序列的中位数的 C 语言代码实现：

#include <stdio.h>
#define MAX 100

typedef struct {
    int r[MAX];  // 用数组表示顺序表
    int length;  // 顺序表长度
} Rectype;

// 取顺序表中位数
int Median(Rectype R){
    int s = R.length / 2;
    if(R.length % 2 == 0){
        return (R.r[s-1] + R.r[s]) / 2;
    }
    else{
        return R.r[s];
    }
}

// 求两个等长有序序列的中位数
int search(Rectype A[], Rectype B[], int n){
    int mid1, mid2;
    mid1 = mid2 = Median(A[0]);  // 初始时，中位数为 A[0] 的中位数
    if(n == 1){
        return A[0].r[0] < B[0].r[0] ? A[0].r[0] : B[0].r[0];
    }
    if(A[0].r[mid1] == B[0].r[mid2]){
        return A[0].r[mid1];
    }
    else if(A[0].r[mid1] < B[0].r[mid2]){
        search(A+1, B, n/2 + n%2);
        search(A, B+1, n/2);
    }
    else{
        search(A, B+1, n/2 + n%2);
        search(A+1, B, n/2);
    }
}

int main(){
    int n;
    Rectype A[1], B[1];
    scanf("%d", &n);
    A[0].length = n;
    B[0].length = n;
    for(int i = 0; i < n; i++){
        scanf("%d", &A[0].r[i]);
    }
    for(int i = 0; i < n; i++){
        scanf("%d", &B[0].r[i]);
    }
    printf("A: ");
    for(int i = 0; i < n; i++){
        printf("%d ", A[0].r[i]);
    }
    printf("\nB: ");
    for(int i = 0; i < n; i++){
        printf("%d ", B[0].r[i]);
    }
    printf("\n");

    int mid = search(A, B, n);
    printf("mid=%d", mid);
    return 0;
}

在该程序中，我们定义了一个 Rectype 结构体来表示顺序表，其中 r 数组表示顺序表，length 表示顺序表长度。接着，我们定义了一个 Median 函数来求顺序表的中位数。在 search 函数中，我们首先求出 A 和 B 的中位数 mid1 和 mid2，然后比较 mid1 和 mid2 的大小关系，进行递归调用。最后输出中位数。

注意：在递归调用 search 函数时，需要将 A 和 B 的指针分别加上 n/2 + n%2 和 n/2（即均分序列），避免越界。