使用优先级队列的排序列表的迭代器

Question

我找到了下面的面试题here.

SortedIterator - consists of List of Lists with sorted int values in each list. You have to give next sorted value when call next().

have to implement methods * constructor * 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)

Space: O (N * K) 存储扁平化列表。

N - 列表数。

K - 每个列表中的元素数。

但是 link 中的 answer 说：

There is a solution with time complexity O(logN) using a priority queue. Maybe an interviewer expected something like that, I don't know.

O (log N)怎么可能？如果使用优先级队列，每次调用 hasNext() 时，我们都需要检查队列是否为空 (O(1))。然后我们调用 next()，它根据 table 从队列（O(log (N*K)）中提取最小元素（对于任何实现）。由于我们需要调用 next() N * K 次，因此我们需要 O(N * K * log (N*K) 遍历所有元素。

Answer 1

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

解决方案看起来像这样：

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

请注意，该解决方案不会同时将所有 N*K 值保留在优先级队列中，仅保留 N 个列表中每个列表中的单个 "next" 值。因此，优先级队列始终（最多）有 N 个元素，因此它的操作都是 O(log N)。

要理解为什么会这样，请记住每个列表都已经排序，因此最小未使用值必须出现在某些列表的 "front" 处（不包括已使用的值）。然后，请注意优先级队列恰好包含每个列表的 "front" 元素——当我们从与该元素相同的列表中将元素添加到 pq 时，我们强制在 next() 中发生这种情况我们删除了。因此，在任何时候 pq 都将包含最小未使用值（直到所有值都用完）。

使用优先级队列的排序列表的迭代器

Iterator for a list of sorted lists using a priority queue

java

algorithm

priority-queue

data-structures