我发现以下面试问题 在这里。
时间复杂度:展平输入的列表所需的 O(K * N) 时间 + 遍历展平后列表所需的 O(N*K) 时间 = O(N * K)。
空间复杂度:存储展平后列表所需的 O(N * K) 空间。
其中,N 为列表数目,K 为每个列表中元素的数目。
但是来自链接 answer 的答案说:
“有一种使用优先队列的时间复杂度为 O(logN) 的解法。也许面试官期望得到这样的答案,我不确定。”
如果使用优先队列,每次调用
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)
的时间。
nestedList.stream().flatMap(identity()).sorted().iterator()
。 - Boris the SpiderSortedIterator
时应用程序挂起几秒钟。预计算复杂度和每个元素的复杂度之间总是存在权衡。 - k_ssb