使用优先队列实现已排序列表的迭代器

Question

我发现以下面试问题 在这里。

SortedIterator - 由每个列表中都有排序的整数值的列表组成。当调用next（）时，您必须给出下一个排序值。

必须实现方法 * 构造函数 * next() * hasNext()

[ [1, 4, 5, 8, 9], [3, 4, 4, 6], [0, 2, 8] ]

next() -> 0, 1, 2, 3, 4, 4, 4...

我用Java写了一个快速实现：

package com.app;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class SortedIterator implements Iterator<Integer> {

    private final List<Integer> mFlattenedList;
    private final Iterator<Integer> mIntegerIterator;

    SortedIterator(final List<List<Integer>> lists) {
        mFlattenedList = flattenLists(lists);
        mIntegerIterator = mFlattenedList.iterator();
    }

    private List<Integer> flattenLists(final List<List<Integer>> lists) {
        final List<Integer> result = new ArrayList<>();
        for (List<Integer> list : lists) {
            for (int value : list) {
                result.add(value);
            }
        }
        Collections.sort(result);
        return result;
    }

    @Override
    public boolean hasNext() {
        return mIntegerIterator.hasNext();
    }

    @Override
    public Integer next() {
        return mIntegerIterator.next();
    }
}

时间复杂度：展平输入的列表所需的 O(K * N) 时间 + 遍历展平后列表所需的 O(N*K) 时间 = O(N * K)。

空间复杂度：存储展平后列表所需的 O(N * K) 空间。

其中，N 为列表数目，K 为每个列表中元素的数目。

但是来自链接 answer 的答案说：

“有一种使用优先队列的时间复杂度为 O(logN) 的解法。也许面试官期望得到这样的答案，我不确定。”

如果使用优先队列，每次调用hasNext()时，我们需要检查队列是否为空(O(1))。然后我们调用next()从队列中提取最小元素(O(log (N*K))对于任何实现)根据table。由于我们需要调用next()N * K次，所以遍历所有元素需要O(N * K * log (N*K)的时间。

- Maksim Dmitriev

---

nestedList.stream().flatMap(identity()).sorted().iterator()。 - Boris the Spider

@BoristheSpider 这基本上就是OP正在做的事情，但每个元素并没有得到O(log N)的复杂度。 - k_ssb

假设整个数据被消耗，对于n个元素，“O(n lg n)”肯定是每个元素“O(lg n)”。 - Boris the Spider

@BoristheSpider，我相信您不希望在构建巨大的SortedIterator时应用程序挂起几秒钟。预计算复杂度和每个元素的复杂度之间总是存在权衡。 - k_ssb

在假设此操作在启动时执行而不是每个操作执行一次，并且可以以某种方式检测到此延迟的情况下，是的。例如，如果这是一个微服务，每个请求只运行一次，那么没有区别。从根本上讲，@pkpnd，你是正确的，这是吞吐量与延迟的问题 - 但我不喜欢这些“可爱”的算法问题，因为它们通常在实践中不相关。 - Boris the Spider

Answer 1

该解决方案的复杂度 O(logN) 是每个元素的复杂度，而不是迭代所有值的复杂度。

该解决方案如下：

1. 首先定义一个名为 ListValue 的新类，它将一个值以及它来自的列表的索引存储起来。这些应该可以与其他 ListValue 对象进行比较，使用值进行比较。 2. 构造函数：初始化一个名为 pq 的 PriorityQueue，并将 N 个列表中的第一个元素放入 pq 中。 3. next()：弹出 pq 前面的 ListValue。其中的值是要返回的值，但首先要将该 ListValue 的列表中的下一个元素移动到 pq 中。复杂度为 O(log N)，因为我们从 pq 中删除一个元素并添加一个元素，pq 最多包含 N 个元素。

请注意，该解决方案并没有同时保留所有 N*K 个值在优先队列中，而只保留了 N 个列表中的单个“下一个”值。因此，优先队列始终具有（最多）N 个元素，因此其操作都是 O(log N)。

要理解为什么这样做有效，请记住每个列表已经排序，因此未使用的最小值必须出现在某个列表的“前面”（不包括已消耗的值）。然后，注意优先队列恰好包含每个列表的“前面”元素——我们在 next() 中强制执行这一点，当我们从与我们删除的元素相同的列表中向 pq 添加一个元素时。因此，在任何时候 pq 都将包含最小未使用值（直到所有值都用完）。

- k_ssb