本文共 747 字，大约阅读时间需要 2 分钟。

为了求解两个非降序序列S1和S2的并集的中位数，我们可以使用双指针法来高效找到中位数。具体步骤如下：

通过这种方法，我们可以在O(n)的时间复杂度内找到并集的中位数，适合处理大数据量。

步骤解释中的示例代码理解：

def find_median(S1, S2):
    n = len(S1)
    i = j = 0
    m = (2 * n - 1) // 2  # 目标索引
    while i + j < m:
        if S1[i] <= S2[j]:
            i += 1
        else:
            j += 1
    # 如果超出数组，直接返回最后一个数
    # 否则比较剩下的数并返回较大的
    return max(S1[i], S2[j] if i + j == m else S1[i], S2[j] if i + j == m else max(S1[i], S2[j]))
n = int(input())
S1 = list(map(int, input().split()))
S2 = list(map(int, input().split()))
print(find_median(S1, S2))

代码逻辑简单明了，利用双指针法，高效地求得并集的中位数。

转载地址：http://bkbwk.baihongyu.com/