Java代码审查：将排序列表合并到单个排序列表中

Question

已关闭 。这个问题是基于观点的。它当前不接受答案。

想改善这个问题吗？ 更新问题，以便通过编辑此帖子以事实和引用的形式回答。

7年前关闭。

改善这个问题

我想将排序的列表合并到一个列表中。这个解决方案如何？我相信它运行时间为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

您的解决方案可能是最快的解决方案。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对象作为输入，并且最低的对象可以初始化为list.get（0），并且可以跳过null检查。