This question already has an answer here:
Given K sorted lists of up to N elements in each list, return a sorted iterator over all the items
(1个答案)
2年前关闭。
我发现以下面试问题here.
SortedIterator-由列表列表组成,列表中具有排序的int值
每个列表。调用next()时必须提供下一个排序的值。
必须实施方法
*构造函数
* 下一个()
* hasNext()
[[1,4,5,8,9],[3,4,4,6],[0,2,8]]
next()-> 0,1,2,3,4,4,4 ...
我用Java编写了一个快速实现:
时间:用O(K * N)展平输入列表+ O(N * K)遍历展平列表= O(N * K)
空格:O(N * K)存储展平的列表。
N-列表数。
K-每个列表中的元素数。
但是链接中的answer表示:
有一个使用优先级的时间复杂度为O(logN)的解决方案
队列。也许一个面试官期望这样的事情,我不
知道。
首先定义一个名为 构造函数:初始化一个称为 next():弹出
请注意,该解决方案不会一次将所有N * K个值都保留在优先级队列中,而是仅从N个列表中的每一个中获取一个“next”值。因此,优先级队列始终具有(最多)N个元素,因此其操作均为O(log N)。
要了解为什么这样做,请记住每个列表已经排序,因此最小未使用值必须出现在某个列表的“前部”(不包括已经消耗的值)。然后,请注意,优先级队列恰好包含每个列表的“前”元素-当我们从与删除元素相同的列表中向
(1个答案)
2年前关闭。
我发现以下面试问题here.
SortedIterator-由列表列表组成,列表中具有排序的int值
每个列表。调用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)的解决方案
队列。也许一个面试官期望这样的事情,我不
知道。
O (log N)
怎么可能?如果使用了优先级队列,则每次调用hasNext()
时,我们都需要检查队列是否为空(O(1)
)。然后我们调用next()
,它根据table从队列中提取min元素(对于任何实现,都是O(log (N*K)
)。由于我们需要调用next()
N * K次,因此需要O(N * K * log (N*K)
来迭代所有元素。 最佳答案
解决方案的O(logN)复杂度是每个元素的复杂度,而不是迭代所有值的复杂度。
解决方案如下所示:
ListValue
的新类,该类存储值以及它来自的列表的索引。这些应该与使用该值的其他ListValue
对象相当。 PriorityQueue<ListValue>
的pq
,并将N个列表中的每个列表的第一个元素放入pq
中。 ListValue
前面的pq
。内部的值是要返回的值,但首先,将ListValue
列表中的下一个元素移到pq
中。复杂度为O(log N),因为我们删除了一个元素,然后向pq
添加了一个元素,next()
最多包含N个元素。 请注意,该解决方案不会一次将所有N * K个值都保留在优先级队列中,而是仅从N个列表中的每一个中获取一个“next”值。因此,优先级队列始终具有(最多)N个元素,因此其操作均为O(log N)。
要了解为什么这样做,请记住每个列表已经排序,因此最小未使用值必须出现在某个列表的“前部”(不包括已经消耗的值)。然后,请注意,优先级队列恰好包含每个列表的“前”元素-当我们从与删除元素相同的列表中向
pq
添加元素时,我们强制在pq
中发生。因此,ojit_code始终会包含最小的未使用值(直到所有值都用尽)。