我有两个包含整数的不同列表,我需要不断地找到这两个列表之间的两个最小值;我应该指出,我不想将这两个列表合并在一起,因为它们是不同的类型。
我想知道我的方法是好是坏。如果不好,请让我知道如何提高效率。
始终按降序对两个列表进行排序,因此分钟将在底部
从 list1 中找到两分钟并将其与 list2 中的两分钟进行比较,然后从这四个值中找到两分钟
从关联列表中删除两个分钟,将它们的值组合在一起(必需)并将其添加到列表 2
我实际上是在执行 Huffman 代码的一部分,我想在其中按降序排列字符的频率列表。
最佳答案
在 List
中查找最小值可以在线性时间内完成,无需任何排序。每次排序和查找最小值将是 O(m*nlgn)
m 是迭代次数,n 是列表的大小)。
更好的方法是使用 PriorityQueue
(最小堆),其中最小值始终位于堆的顶部,而不是在每次迭代时都进行排序。
min-heap
通常用于实现 Huffman 代码
和一般的贪心算法。
关于java - 如何不断地从两个不同的列表中找到两个最小值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37171117/