Java代码审查:将已排序的列表合并为单个排序列表

Question

我想将排序列表合并到一个列表中.这个解决方案怎么样？我相信它会在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;
}

注意:这不是作业,但它也不适用于生产代码.

Answer 1

如果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)中,并且远远不那么繁琐的代码来测试,调试和维护.

Answer 2

扩展安东的评论:

通过将每个List的最新结果以及它的列表指示符放入堆中,然后不断地从堆中取出顶部,并从属于您刚刚获取的项的列表中将新项放入堆中关闭.

Java的PriorityQueue可以提供堆实现.

Answer 3

您的解决方案可能是最快的解决方案。SortedList 的插入成本为 log(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)，并且可以跳过空检查。