java - 如何不断地从两个不同的列表中找到两个最小值？

Question

我有两个包含整数的不同列表，我需要不断地找到这两个列表之间的两个最小值；我应该指出，我不想将这两个列表合并在一起，因为它们是不同的类型。

我想知道我的方法是好是坏。如果不好，请让我知道如何提高效率。

• 始终按降序对两个列表进行排序，因此分钟将在底部

• 从 list1 中找到两分钟并将其与 list2 中的两分钟进行比较，然后从这四个值中找到两分钟

• 从关联列表中删除两个分钟，将它们的值组合在一起(必需)并将其添加到列表 2

我实际上是在执行 Huffman 代码的一部分，我想在其中按降序排列字符的频率列表。

Answer 1

在 List 中查找最小值可以在线性时间内完成，无需任何排序。每次排序和查找最小值将是 O(m*nlgn) m 是迭代次数，n 是列表的大小)。

更好的方法是使用 PriorityQueue(最小堆)，其中最小值始终位于堆的顶部，而不是在每次迭代时都进行排序。

min-heap 通常用于实现 Huffman 代码 和一般的贪心算法。