Java代码审查：将已排序的列表合并到单个排序列表中 [英] Java Code Review: Merge sorted lists into a single sorted list

问题描述

我想将排序列表合并到一个列表中。这个解决方案怎么样？我相信它会在O（n）时间内运行。任何明显的缺陷，效率低下或风格问题？

I want to merge sorted lists into a single list. How is this solution? I believe it runs in O(n) time. Any glaring flaws, inefficiencies, or stylistic issues?

我真的不喜欢为这是第一次迭代设置标志的习惯用法并用它来制作确保最低具有默认值。有更好的方法吗？

I don't really like the idiom of setting a flag for "this is the first iteration" and using it to make sure "lowest" has a default value. Is there a better way around that?

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;
}

注意：这不是作业，但不适用于生产代码，或者。

Note: this isn't homework, but it isn't for production code, either.

推荐答案

您的解决方案可能是最快的解决方案。 SortedLists的插入成本为log（n），因此您最终会得到M log（M）（其中M是列表的总大小）。

Your solution is probably the fastest one. SortedLists have an insert cost of log(n), so you'll end up with M log (M) (where M is the total size of the lists).

将它们添加到一个列表并排序，同时更容易阅读，仍然是M log（M）。

Adding them to one list and sorting, while easier to read, is still M log(M).

您的解决方案只是M。

您可以通过调整结果列表的大小来清理代码，并使用对最低列表的引用而不是布尔值。

You can clean up your code a bit by sizing the result list, and by using a reference to the lowest list instead of a boolean.

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），您可以跳过空检查。

If you're really particular, use a List object as input, and lowest can be initialized to be lists.get(0) and you can skip the null check.

这篇关于Java代码审查：将已排序的列表合并到单个排序列表中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！