中等
技术面试0 次浏览给定一个包含多个有序列表的列表,每个有序列表中的元素都是整数,请编写一个 Python 函数,将这些列表合并成一个有序列表。要求时间复杂度尽可能低。
微软中国数据分析师
Python算法排序
答题要点
可以采用分治法的思路来解决。关键要点:首先,将多个有序列表两两合并,不断重复这个过程,直到只剩下一个有序列表。其次,使用归并排序的思想,在合并两个有序列表时,比较两个列表的当前元素,将较小的元素添加到结果列表中。然后,移动指针,继续比较,直到其中一个列表遍历完。最后,将另一个列表的剩余元素添加到结果列表中。示例思路:定义一个合并两个有序列表的辅助函数,然后在主函数中不断调用该辅助函数进行两两合并。代码示例:def merge_two_lists(l1, l2): result = [] i, j = 0, 0 while i < len(l1) and j < len(l2): if l1[i] < l2[j]: result.append(l1[i]) i += 1 else: result.append(l2[j]) j += 1 result.extend(l1[i:]) result.extend(l2[j:]) return result def merge_lists(lists): if not lists: return [] while len(lists) > 1: new_lists = [] for i in range(0, len(lists), 2): if i + 1 < len(lists): new_lists.append(merge_two_lists(lists[i], lists[i + 1])) else: new_lists.append(lists[i]) lists = new_lists return lists[0]