使用优先级队列的排序列表的迭代器[重复]

我发现了下面的面试问题 here.

*建造师 *下一个() *hasNext()

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

下一步()->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)

N-列表数。

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

answer 链接上写着:

排队。也许一个面试官期待这样的事情,我不知道

怎么样 O (log N) 可能吗?如果使用了优先级队列,每次调用 hasNext() ,我们需要检查队列是否为空( O(1) next() 从队列中提取min元素( O(log (N*K) )根据 table . 既然我们需要打电话 下一个() N*K次,我们 O(N * K * log (N*K) 迭代所有元素。