c*******r
发帖数: 309 | 1 这题到底具体应该怎么解啊？ 临近面试发现又什么都不会了。。。。
有N个pointer指向N个array的头，然后binary search这N个element然后找到最大的
insert到heap.
time complexity :O(logN*totallength)
或者直接建一个k size maxheap,然后insert所有元素
time complexity : O(logK*totallength) |
r**********a
发帖数: 71 | 2 你的第一个做法，这N个头不是有序的，怎么binary search? 必须线性时间才能找到最
大的吧. |
o****d
发帖数: 2835 | 3 maintain a heap of size N, insert all first elements of arrays.
each time, extract the largest one and insert the next element in the same
array
time complexity O(K logN)
any better solution?
【在 c*******r 的大作中提到】
: 这题到底具体应该怎么解啊？ 临近面试发现又什么都不会了。。。。
: 有N个pointer指向N个array的头，然后binary search这N个element然后找到最大的
: insert到heap.
: time complexity :O(logN*totallength)
: 或者直接建一个k size maxheap,然后insert所有元素
: time complexity : O(logK*totallength)
|
r**h
发帖数: 1288 | 4 1.找最大K个的话应该是minHeap吧？每次pop掉最小的
2.这个应该和外排序的N way merge一样吧？可以用tournament tree或者heap，不过
heap的size应该是2N-1
【在 o****d 的大作中提到】
: maintain a heap of size N, insert all first elements of arrays.
: each time, extract the largest one and insert the next element in the same
: array
: time complexity O(K logN)
: any better solution?
|
a*******3
发帖数: 27 | 5 对N个数组中的最大元素开始做二分，找到一个最小的m，是的N个数组中恰好有>=k个数
小于等于m，那么m就是所求。
每次求N个数组中多少个元素小于等于m，nlogn，最多二分32或者64次（取决于数据是
32位还是64位），这样看的话是nlogn的，只不过常数有点大
如果不认为这个实常数，那么就是nlog(n)log(max_value-min_value)
klogn的问题是，k可能很大，如果k~n^2/2，那复杂度就高上去了 |
r**h
发帖数: 1288 | 6 那使用一个大小为k的heap呢
第一次取第一个数组中的前k个元素，如果长度小于k的话就取第二个数组，直到取到k
个元素建堆。然后顺序处理每个数组前k个元素，更新这个堆。总时间应该是
O(nk * log k)。不过在总元素数量非常大内存装不下的时候，这种方法的I/O次数比O(
k log n)的方法少。
绕晕了。。。求指导
【在 a*******3 的大作中提到】
: 对N个数组中的最大元素开始做二分，找到一个最小的m，是的N个数组中恰好有>=k个数
: 小于等于m，那么m就是所求。
: 每次求N个数组中多少个元素小于等于m，nlogn，最多二分32或者64次（取决于数据是
: 32位还是64位），这样看的话是nlogn的，只不过常数有点大
: 如果不认为这个实常数，那么就是nlog(n)log(max_value-min_value)
: klogn的问题是，k可能很大，如果k~n^2/2，那复杂度就高上去了
|
o****o
发帖数: 23 | 7 既然是sorted（假设是从大到小），就用一个size n的最大堆，每次取出最大的，然后
加入该元素所在数组的后续元素，heapify之后再取，直到取到top K停止。
如果不是sorted，那就得用size k的最小堆，遍历所有array的剩余元素，分别与最小
堆的root比较，大于root就替换root，heapify一下，小于等于就跳过。 |
D**********d
发帖数: 849 | 8 到底是 k >> N 还是 N << k?
如果 N array 连头元素的排序也没有，那至少要建个 size k 的 heap 来排头元素啊,
这样要 N*lgk, 剩下还要 k*lgk 找出前k个 |
q*******z
发帖数: 62 | 9 根据三楼的做法，用C++写了一个，根据STL的文档应该是O(N+K)的时间复杂度，空间复
杂度不太清楚：
vector topK(vector> arrs, int N, int K)
{
priority_queue a;
unordered_multimap idxs;
for(int i = 0; i < N; i++)
{
if(!arrs[i].empty())
{
idxs.insert(make_pair(arrs[i].back(),i));
a.push(arrs[i].back());
arrs[i].pop_back();
}
}
vector r;
for(int i = 0; i < K; i++)
{
int val = a.top();
a.pop();
r.push_back(val);
auto it = idxs.find(val);
int k = it->second;
idxs.erase(it);
if(!arrs[k].empty())
{
idxs.insert(make_pair(arrs[k].back(),k));
a.push(arrs[k].back());
arrs[k].pop_back();
}
}
return r;
} |
c*******r
发帖数: 309 | 10 还是没搞懂。如果是N个sorted array...是应该建大小为k的max heap么？ 然后每个
array的指针往heap里insert，都和root比，如果比root大的话就更换 |
|
|
c*******r
发帖数: 309 | 11 还是没搞懂。如果是N个sorted array...是应该建大小为k的max heap么？ 然后每个
array的指针往heap里insert，都和root比，如果比root大的话就更换 |
o****d
发帖数: 2835 | 12 why it is O(N+K)
do you mean the amortized complexity?
I understand that if it the heap is implemented as a Fibonacci heap, the
complexity of insert is amortized O(1), extract can also O(1)
【在 q*******z 的大作中提到】
: 根据三楼的做法，用C++写了一个，根据STL的文档应该是O(N+K)的时间复杂度，空间复
: 杂度不太清楚：
: vector topK(vector> arrs, int N, int K)
: {
: priority_queue a;
: unordered_multimap idxs;
: for(int i = 0; i < N; i++)
: {
: if(!arrs[i].empty())
: {
|
q*******z
发帖数: 62 | 13 因为所有操作都是O(1)啊，STL 的priority queue的操作都是O(1),hash table 也是O(
1)
【在 o****d 的大作中提到】
: why it is O(N+K)
: do you mean the amortized complexity?
: I understand that if it the heap is implemented as a Fibonacci heap, the
: complexity of insert is amortized O(1), extract can also O(1)
|
o****d
发帖数: 2835 | 14 yes, O(1) should be amortized time cost, including hashtable.
O(
【在 q*******z 的大作中提到】
: 因为所有操作都是O(1)啊，STL 的priority queue的操作都是O(1),hash table 也是O(
: 1)
|
d*******3
发帖数: 58 | 15 不对吧，prioriy queue push 操作是logn的
O(
【在 q*******z 的大作中提到】
: 因为所有操作都是O(1)啊，STL 的priority queue的操作都是O(1),hash table 也是O(
: 1)
|
