Python 列表合并题 – Jacky's Blog

完成 merge(L1, L2) 函数：输入参数是两个从小到大排序好的整数列表 L1 和 L2，
返回合成后的从小到大排序好的大列表 X

例如 merge([1,4,5], [2, 7, 11]) 会返回 [1,2,4,5,7]; merge([], [2,3,4]) 会返回 [2,3,4]
[1, 5, 7, 9], [2,4,6]
要求:
(1) 程序中比较两个元素大小的次数不能超过 len(L1) + len(L2)
(2) 只能用列表 append() 和 len() 函数
高中舍友给我发的题

很迷，这道题想了好久，写了好几种解法，然后发布这篇文章之前又改了一次。现在的方案和代码量是我能想到的最优解。

难点在于如何在程序比较两个元素大小的次数不能超过 len(L1) + len(L2) 显然桶排序（o(2*(m+n)）、冒泡排序（o(n^2)）、快速排序（o(nlogn)）统统不能用。好在给定的两个数列都已经排序好了，这里用归并排序。

先来个循环，对两个列表分别计数，每一步都取最小值到新列表，比如取到l1[0] 下一个循环就让 l1[1]跟 l2[0] 比较，以此类推。如果有一个列表全部元素都已经被比较完了并全部加入新列表中了，就直接让另一个列表内的剩下的元素加到新列表后面。

经过这波操作之后，最大比较次数为 len(l1)+len(l2) -1，某些情况下比较次数会降到 1/3[ len(l1)+len(l2) ]

下面是实现的代码

# 时间复杂度 n(n) n < len(1)+len(2)
def merge(l1, l2):
    l1_length = len(l1)
    l2_length = len(l2)
    
    if l1_length is 0:
        return l2
    if l2_length is 0:
        return l1
    
    x = []
    i = 0
    j = 0
    m = 0

    while True:
        m += 1
        if l1[i] < l2[j]:
            x.append(l1[i])
            if i < l1_length - 1:
                i += 1
            else:
                for s in l2[j:]:
                    x.append(s)
                break
        else:
            x.append(l2[j])
            if j < l2_length - 1:
                j += 1
            else:
                for l in l1[i:]:
                    x.append(l)
                break

    print('两个列表的长度和 %s 比较次数 %s' % (l1_length + l2_length, m))
    return x

文章最后修订于 2021年6月23日

Python