T1031-锅一（卢梓鸿）

A.有序序列合并：双指针

• 时间复杂度：O(n+m)
• 空间复杂度：O(1)

思路

初始化指针为两个序列的头指针，根据双指针所指的值比较大小将小值加入合并序列并指针前进一步，注意当其中一个指针到序列尾部时可以将另一个序列剩余部分直接加入合并序列。

代码

n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
res = []
j = k = 0
while j != n or k != m:
    if j == n:
        res = res + b[k:]
        k = m
    elif k == m:
        res = res + a[j:]
        j = n
    else:
        if a[j] > b[k]:
            res.append(b[k])
            k += 1
        else:
            res.append(a[j])
            j += 1
for i in res:
    print(i, end=" ")