求两个等长序列中位数

假设两个等长序列分别为 A 和 B，它们的长度都为 n。

求两个等长序列的中位数可以转化为求它们合并后的有序序列的中位数。

具体的做法是：

1. 将 A 和 B 合并成一个长度为 2n 的序列 C，其中 C[0] 到 C[n-1] 是 A 中的元素，C[n] 到 C[2n-1] 是 B 中的元素。

2. 对序列 C 进行排序。

3. 如果 n 是奇数，那么中位数就是 C[n/2]。

4. 如果 n 是偶数，那么中位数就是 (C[n/2-1] + C[n/2])/2。

下面是一个 Python 代码实现：

def median_of_two_sorted_arrays(A, B):
    n = len(A)
    C = A + B
    C.sort()
    if n % 2 == 1:
        return C[n // 2]
    else:
        return (C[n // 2 - 1] + C[n // 2]) / 2

其中，A 和 B 分别是两个等长序列。函数返回它们的中位数。

相关问题

求两个序列的中位数代码

假设有两个长度分别为 m 和 n 的有序数组 nums1 和 nums2。为了找到两个数组的中位数，需要将两个数组合并成一个有序数组，并找到这个有序数组的中位数。

以下是一种常见的解法，时间复杂度为 O(log(m+n))：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1); // 保证 nums1 的长度小于等于 nums2 的长度
        }
        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && nums2[j - 1] > nums1[i]) {
                iMin = i + 1; // i 太小了，需要右移
            } else if (i != 0 && j != n && nums1[i - 1] > nums2[j]) {
                iMax = i - 1; // i 太大了，需要左移
            } else { // i 刚好合适，或 i 已经移动到边界
                int maxLeft = 0;
                if (i == 0) { maxLeft = nums2[j - 1]; }
                else if (j == 0) { maxLeft = nums1[i - 1]; }
                else { maxLeft = max(nums1[i - 1], nums2[j - 1]); }
                if ((m + n) % 2 == 1) { return maxLeft; } // 如果大数组的长度是奇数，中位数就是左半部分的最大值
                int minRight = 0;
                if (i == m) { minRight = nums2[j]; }
                else if (j == n) { minRight = nums1[i]; }
                else { minRight = min(nums2[j], nums1[i]); }
                return (maxLeft + minRight) / 2.0; // 如果大数组的长度是偶数，取左侧最大值和右侧最小值的平均数为中位数
            }
        }
        return 0.0;
    }
};

这个算法的基本思想是，将数组 nums1 和 nums2 分别划分为两部分 leftPart 和 rightPart，使得 leftPart 中的元素都小于 rightPart 中的元素，然后中位数就是 leftPart 中的最大值和 rightPart 中的最小值的平均数。为了满足这个条件，需要满足以下两个条件：

1. len(leftPart) == len(rightPart) （两个数组的长度之和是偶数）
或者
2. len(leftPart) == len(rightPart) + 1 （两个数组的长度之和是奇数）

在算法中，使用 i 和 j 分别表示 nums1 和 nums2 中分割线的位置，iMax 和 iMin 分别表示二分查找的上下界。在每次迭代中，根据 nums1[i-1] 和 nums2[j-1] 的大小关系，调整 iMax 或 iMin 的值，直到找到合适的 i 和 j。

寻找两个等长有序序列的中位数设计的技术难点

寻找两个等长有序序列的中位数的技术难点主要是如何在时间复杂度为 O(log n) 的情况下完成。具体来说，需要采用分治算法的思想，将问题不断划分成规模更小的子问题，直到达到最小的情况，然后再将子问题的解合并起来得到原问题的解。在这个过程中，需要考虑以下几个难点：

1. 如何确定两个序列的中位数的位置

在合并两个有序序列的过程中，需要确定这两个序列的总长度以及中位数的位置。如果两个序列的长度都为偶数，那么中位数的位置就是两个位置，需要找到这两个位置对应的数并取平均值作为中位数；如果长度都为奇数，那么中位数的位置就是一个位置，需要直接找到这个位置对应的数。因此，需要先计算出两个序列的长度，然后根据长度来确定中位数的位置。

2. 如何将两个有序序列合并成一个有序序列

在确定了中位数的位置之后，需要将两个有序序列合并成一个有序序列，然后再根据中位数的位置来确定中位数。这个过程可以采用归并排序的思想，即每次比较两个序列中的第一个数，将较小的数放入结果序列中，然后继续比较两个序列中的下一个数，直到其中一个序列为空，然后将另一个序列中的剩余元素直接放入结果序列中。

3. 如何确定中位数的位置在哪个序列中

在合并两个有序序列的过程中，需要确定中位数的位置在哪个序列中。可以采用递归的思想，在每次合并两个序列时，判断中位数的位置与当前序列的长度的关系，如果中位数的位置小于当前序列的长度的一半，则说明中位数在当前序列的前半部分，否则就在后半部分，然后递归处理前半部分或后半部分，直到找到中位数所在的序列为止。

4. 如何处理奇偶性

如果两个序列的长度都为偶数，那么需要找到中间的两个数并取平均值作为中位数；如果长度都为奇数，那么直接找到中间的数作为中位数。因此，需要在程序中对奇偶性进行判断，并根据不同的情况来确定中位数。