Java Code Review:将已排序列表合并为单个已排序列表
我想将已排序的列表合并到一个列表中。这个解决方案怎么样？我相信它的运行时间是O(n)。是否有明显的缺陷、低效或风格问题？
我真的不喜欢为“这是第一次迭代”设置标志，并用它来确保“最低”有一个默认值的习惯用法。有没有更好的方法来解决这个问题？
public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) {
List<T> result = new ArrayList<T>();
int totalSize = 0; // every element in the set
for (List<T> l : lists) {
totalSize += l.size();
}
boolean first; //awkward
List<T> lowest = lists.iterator().next(); // the list with the lowest item to add
while (result.size() < totalSize) { // while we still have something to add
first = true;
for (List<T> l : lists) {
if (! l.isEmpty()) {
if (first) {
lowest = l;
first = false;
}
else if (l.get(0).compareTo(lowest.get(0)) <= 0) {
lowest = l;
}
}
}
result.add(lowest.get(0));
lowest.remove(0);
}
return result;
}注意:这不是作业，但也不是针对产品代码的。
回答 5
Stack Overflow用户
发布于 2009-11-21 23:18:34
您的解决方案可能是最快的。log的插入开销为SortedLists (N)，因此最终将得到M log (M) (其中M是列表的总大小)。
将它们添加到一个列表中并进行排序，虽然更容易阅读，但仍然是M log(M)。
你的解决方案就是M。
您可以通过调整结果列表的大小，以及使用对最低列表的引用而不是布尔值来清理代码。
public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) {
int totalSize = 0; // every element in the set
for (List<T> l : lists) {
totalSize += l.size();
}
List<T> result = new ArrayList<T>(totalSize);
List<T> lowest;
while (result.size() < totalSize) { // while we still have something to add
lowest = null;
for (List<T> l : lists) {
if (! l.isEmpty()) {
if (lowest == null) {
lowest = l;
} else if (l.get(0).compareTo(lowest.get(0)) <= 0) {
lowest = l;
}
}
}
result.add(lowest.get(0));
lowest.remove(0);
}
return result;
}如果你真的很特别，可以使用List对象作为输入，最低值可以初始化为lists.get(0)，并且可以跳过null检查。
Stack Overflow用户
发布于 2009-11-21 21:43:00
如果lists包含一个ArrayList，那么效率将会很差，因为lowest.remove(0)将占用列表长度的线性时间，使得您的算法为O(n^2)。
我会这么做：
List<T> result = new ArrayList<T>();
for (List<T> list : lists) {
result.addAll(list);
}
Collections.sort(result);这是O(n log n)，并且留下的测试、调试和维护的繁琐代码要少得多。
Stack Overflow用户
发布于 2009-11-21 10:26:06
对Anton的评论进行扩展：
通过将来自每个列表的最新结果以及它是哪个列表的指示器放入堆中，然后不断地从堆中取出顶部，并将属于您刚刚取出的项的列表中的一个新项放入堆中。
Java的PriorityQueue可以提供堆实现。
https://stackoverflow.com/questions/1774256
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号