Java代码审查：将已排序的列表合并为单个排序列表
我想将排序列表合并到一个列表中。 这个解决方案怎么样？ 我相信它会在O（n）时间内运行。 任何明显的缺陷，效率低下或风格问题？
我真的不喜欢为“这是第一次迭代”设置标志的习惯用法，并使用它来确保“最低”具有默认值。 有更好的方法吗？
public static <T extends Comparable> List merge(Set<List> lists) { List result = new ArrayList(); int totalSize = 0; // every element in the set for (List l : lists) { totalSize += l.size(); } boolean first; //awkward List 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 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; } 注意：这不是作业，但也不适用于生产代码。
您的解决方案可能是最快的。 SortedLists的插入成本为log（n），因此您最终会得到M log（M）（其中M是列表的总大小）。
将它们添加到一个列表并排序，同时更容易阅读，仍然是M log（M）。
你的解决方案就是M.
您可以通过调整结果列表的大小来清理代码，并使用对最低列表的引用而不是布尔值。
public static > List merge(Set> lists) { int totalSize = 0; // every element in the set for (List l : lists) { totalSize += l.size(); } List result = new ArrayList (totalSize); List lowest; while (result.size() < totalSize) { // while we still have something to add lowest = null; for (List 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），并且可以跳过空检查。
如果lists包含ArrayList，效率将会lowest.remove(0) ，因为lowest.remove(0)将占用列表长度的线性时间，使得算法为O（n ^ 2）。
我会做：
List result = new ArrayList (); for (List list : lists) { result.addAll(list); } Collections.sort(result);
它位于O（n log n）中，并且使得测试，调试和维护的代码更加繁琐。
扩展安东的评论：
通过将每个List的最新结果以及它的列表指示符放入堆中，然后不断地从堆中取出顶部，并从属于您刚刚获取的项的列表中将新项放入堆中关闭。
Java的PriorityQueue可以提供堆实现。
这是一个非常古老的问题，但我不喜欢任何提交的答案，所以这就是我最终要做的。
将它们全部添加到一个列表中的解决方案和排序是不好的，因为日志线性复杂性。 如果这对你不重要，那么这绝对是最简单，最直接的答案。 你的初始解决方案并不坏，但它有点乱，而且@Dathan指出m列表和n个元素的复杂度为O（mn）。 您可以使用堆将其减少为O（n log（m）），以减少每个元素的比较次数。 我使用一个帮助程序类，允许我比较迭代。 这样我就不会销毁初始列表，无论输入什么类型的列表，它都应该以合理的复杂度运行。 我在下面的实现中看到的唯一缺陷是它不支持带有null元素的列表，但是如果需要可以修复它。
public static > List merge(Collection> lists) { PriorityQueue> queue = new PriorityQueue>(); for (List list : lists) if (!list.isEmpty()) queue.add(new CompIterator (list.iterator())); List merged = new ArrayList (); while (!queue.isEmpty()) { CompIterator next = queue.remove(); merged.add(next.next()); if (next.hasNext()) queue.add(next); } return merged; } private static class CompIterator > implements Iterator , Comparable> { E peekElem; Iterator it; public CompIterator(Iterator it) { this.it = it; if (it.hasNext()) peekElem = it.next(); else peekElem = null; } @Override public boolean hasNext() { return peekElem != null; } @Override public E next() { E ret = peekElem; if (it.hasNext()) peekElem = it.next(); else peekElem = null; return ret; } @Override public void remove() { throw new UnsupportedOperationException(); } @Override public int compareTo(CompIterator o) { if (peekElem == null) return 1; else return peekElem.compareTo(o.peekElem); } }
返回列表的每个元素都涉及两个O（log（m））堆操作，还有一个对所有列表的初始迭代。 因此，对于n个总元素和m个列表，总体复杂度为O（n log（m）+ m）。 使这总是比连接和排序更快。
由于Balus和meriton一起对你对算法的问题给出了很好的回答，我会对你说“第一”成语。
肯定有其他的方法（比如设置最低到’魔术’值），但我碰巧觉得“第一”（我可能会给它一个更长的名字，但那是迂腐的）是最好的，因为它非常明确。 像“first”这样的布尔值的存在是一个明确的信号，你的循环将在第一次做一些特殊的事情。 它有助于读者。
当然，如果采用Balus / meriton方法，你不需要它，但这是一个突然出现的情况。