面试题：Python列表值灵活运用之高效算法实现

Question

假设有两个有序列表list1和list2，元素都是整数，要求使用Python编写一个高效的算法，将这两个列表合并为一个新的有序列表，并且新列表中的元素不能重复。例如list1 = [1, 3, 5]，list2 = [3, 5, 7]，输出结果应为[1, 3, 5, 7]。请分析该算法的时间复杂度，并说明如何进一步优化。

Answer 1

def merge_lists(list1, list2):
    merged = list(set(list1 + list2))
    merged.sort()
    return merged

时间复杂度分析

1. set(list1 + list2)：
   • 首先执行list1 + list2，这一步的时间复杂度是$O(m + n)$，其中$m$和$n$分别是list1和list2的长度，因为需要遍历两个列表的所有元素。
   • 然后创建set，创建集合的时间复杂度为$O(m + n)$，因为需要将合并后的列表元素插入集合，平均情况下插入每个元素的时间复杂度为$O(1)$。
2. merged.sort()：排序操作的时间复杂度为$O(k log k)$，其中$k$是merged列表的长度，$k \leq m + n$。

综合起来，整体时间复杂度为$O((m + n) + k log k)$，近似为$O((m + n) log(m + n))$，因为$k \leq m + n$。

进一步优化

1. 双指针法：
   • 初始化两个指针，分别指向list1和list2的开头。
   • 创建一个空列表用于存储合并后的结果。
   • 比较两个指针指向的元素，将较小的元素添加到结果列表中，并将对应的指针后移。如果两个元素相等，只添加一个，并将两个指针都后移。
   • 当其中一个列表遍历完后，将另一个列表剩余的元素直接添加到结果列表中。
   • 最后，检查结果列表，去除重复元素。

def merge_lists_optimized(list1, list2):
    result = []
    i = 0
    j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            if not result or list1[i] != result[-1]:
                result.append(list1[i])
            i += 1
        elif list1[i] > list2[j]:
            if not result or list2[j] != result[-1]:
                result.append(list2[j])
            j += 1
        else:
            if not result or list1[i] != result[-1]:
                result.append(list1[i])
            i += 1
            j += 1
    while i < len(list1):
        if not result or list1[i] != result[-1]:
            result.append(list1[i])
        i += 1
    while j < len(list2):
        if not result or list2[j] != result[-1]:
            result.append(list2[j])
        j += 1
    return result

2. 时间复杂度分析（优化后）：
   • 第一个while循环的时间复杂度为$O(m + n)$，因为两个指针最多移动$m + n$次。
   • 后续两个while循环分别处理剩余元素，时间复杂度分别为$O(m)$和$O(n)$。
   • 整体时间复杂度为$O(m + n)$，比之前的$O((m + n) log(m + n))$更优。这种方法避免了先合并再排序的操作，直接在合并过程中保持顺序，并且在合并过程中处理重复元素，提高了效率。