l******i
发帖数: 194 | 1 k nearest points，k most frequent words这种，或者一个n长的array或者什么东西
，output top k elements，到底怎
么做啊～能不能给点code～ |
m*********a
发帖数: 3299 | 2 minHeap
【在 l******i 的大作中提到】
: k nearest points，k most frequent words这种，或者一个n长的array或者什么东西
: ，output top k elements，到底怎
: 么做啊～能不能给点code～
|
l*****a
发帖数: 14598 | 3 1) O(NlogK) O(K) memory
2) O(KlogN) O(N) memory
3) O(N) O(N) memory
【在 l******i 的大作中提到】
: k nearest points，k most frequent words这种，或者一个n长的array或者什么东西
: ，output top k elements，到底怎
: 么做啊～能不能给点code～
|
h***k
发帖数: 161 | 4 第二个为什么不是O(NlogK)呢？
我的想法是先hashmap把所有words数一遍，O(N) memory+time, 然后用k-size的
minheap遍历hashmap,总共是O(NlogK)。
【在 l*****a 的大作中提到】
: 1) O(NlogK) O(K) memory
: 2) O(KlogN) O(N) memory
: 3) O(N) O(N) memory
|
w*******i
发帖数: 186 | 5 时间复杂度都是o（n）吧？本质都是top k问题，马甲不同而已啊。改下comparator，
然后还是用 select algorithm不就行了。 |
x***j
发帖数: 75 | 6 第一个用heap。
第二个是啥？
第三个我猜 quick select？
【在 l*****a 的大作中提到】
: 1) O(NlogK) O(K) memory
: 2) O(KlogN) O(N) memory
: 3) O(N) O(N) memory
|
h***k
发帖数: 161 | 7 agree, 同没看懂第二个
【在 x***j 的大作中提到】
: 第一个用heap。
: 第二个是啥？
: 第三个我猜 quick select？
|
l******i
发帖数: 194 | |
r*******e
发帖数: 971 | 9 以Top K frequent 为例。
1） Min Heap
2） Max Heap
3） Quick Select
【在 x***j 的大作中提到】
: 第一个用heap。
: 第二个是啥？
: 第三个我猜 quick select？
|
h***k
发帖数: 161 | 10 原来如此
【在 r*******e 的大作中提到】
: 以Top K frequent 为例。
: 1） Min Heap
: 2） Max Heap
: 3） Quick Select
|
|
|
s********l
发帖数: 998 | 11 我也这么想的
lollol 说说 为什么 klogn啊？
【在 h***k 的大作中提到】
: 第二个为什么不是O(NlogK)呢？
: 我的想法是先hashmap把所有words数一遍，O(N) memory+time, 然后用k-size的
: minheap遍历hashmap,总共是O(NlogK)。
|
r*******e
发帖数: 971 | 12 遍历HashMap 与List 的contains 有类似之处。
都是存在但是不到万不得已不要用的方法。
【在 h***k 的大作中提到】
: 第二个为什么不是O(NlogK)呢？
: 我的想法是先hashmap把所有words数一遍，O(N) memory+time, 然后用k-size的
: minheap遍历hashmap,总共是O(NlogK)。
|
i*********7
发帖数: 348 | 13 楼上的回答的基本差不多，我就归纳一下吧。
个人理解是这样的，这类型题目基本就两个思路
1. minHeap(PriorityQueue) O(nlogk) time o(k) memory
2. Ranking partitioning(Quicksort的一步) O(N) time no memory(递归call stack
算上的话另说)
minHeap的好处是你可以按序获取前k个，Ranking Partitioning则没有这个功能，只能
帮你找到第k个和前面k - 1个的那一块儿。根据题目采取不同得方案呗。 |
h***k
发帖数: 161 | 14 有大牛指出来是用max-heap
【在 s********l 的大作中提到】
: 我也这么想的
: lollol 说说 为什么 klogn啊？
|
h***k
发帖数: 161 | 15 遍历hashmap的entry就是把array从头到尾扫一遍吧，list的contains是全部扫一遍找
到对应的为止吧。
都是O(n), 这里的遍历hashmap不存在查找的问题吧。。请指教
【在 r*******e 的大作中提到】
: 遍历HashMap 与List 的contains 有类似之处。
: 都是存在但是不到万不得已不要用的方法。
|
r*******e
发帖数: 971 | 16 遍历HashMap实际上是个O（capacity） 最坏情况接近于o（2 ＊n）虽然还是O（n）不
过这题最直接解法也就是这个了。
不那么直接的解法：做个Prefix Tree（Trie），这里需要保证所有word 都只有小写字
母，其实限制很大。
非常不直接的解法：假如知道总数：那么可以做个倒序表：HashSet《String》［total
size＋1］；统计词频时，将单词从倒序表原来位置上删除，放到＋1的位置。这两个
都是O（1）操作，所以平均在O（n＋k）的时间内即可完成。不过注意得把HashSet的
capacity调得比较小才行，否则又会出现第一段的窘境。
坏处是在极端情况，（无重复单词）复杂度会成为o（2n+2k）囧。
【在 h***k 的大作中提到】
: 遍历hashmap的entry就是把array从头到尾扫一遍吧，list的contains是全部扫一遍找
: 到对应的为止吧。
: 都是O(n), 这里的遍历hashmap不存在查找的问题吧。。请指教
|
r*******e
发帖数: 971 | 17 错了Trie不能用来排序，只能省空间以及方便后续查找。
倒序表倒是可以试试，我写一个看看啥么样。
total
【在 r*******e 的大作中提到】
: 遍历HashMap实际上是个O（capacity） 最坏情况接近于o（2 ＊n）虽然还是O（n）不
: 过这题最直接解法也就是这个了。
: 不那么直接的解法：做个Prefix Tree（Trie），这里需要保证所有word 都只有小写字
: 母，其实限制很大。
: 非常不直接的解法：假如知道总数：那么可以做个倒序表：HashSet《String》［total
: size＋1］；统计词频时，将单词从倒序表原来位置上删除，放到＋1的位置。这两个
: 都是O（1）操作，所以平均在O（n＋k）的时间内即可完成。不过注意得把HashSet的
: capacity调得比较小才行，否则又会出现第一段的窘境。
: 坏处是在极端情况，（无重复单词）复杂度会成为o（2n+2k）囧。
|
s********l
发帖数: 998 | 18 我知道是 max-heap 但是觉得复杂度是 O(NlogK) 不是klogn
【在 h***k 的大作中提到】
: 有大牛指出来是用max-heap
|
h***k
发帖数: 161 | 19 赞一个，考虑的很细致！
期待倒序表的解法。。
total
【在 r*******e 的大作中提到】
: 遍历HashMap实际上是个O（capacity） 最坏情况接近于o（2 ＊n）虽然还是O（n）不
: 过这题最直接解法也就是这个了。
: 不那么直接的解法：做个Prefix Tree（Trie），这里需要保证所有word 都只有小写字
: 母，其实限制很大。
: 非常不直接的解法：假如知道总数：那么可以做个倒序表：HashSet《String》［total
: size＋1］；统计词频时，将单词从倒序表原来位置上删除，放到＋1的位置。这两个
: 都是O（1）操作，所以平均在O（n＋k）的时间内即可完成。不过注意得把HashSet的
: capacity调得比较小才行，否则又会出现第一段的窘境。
: 坏处是在极端情况，（无重复单词）复杂度会成为o（2n+2k）囧。
|
h***k
发帖数: 161 | 20 min-heap的话是建一个k大小的堆，遍历完所有N个后剩下的是k个最大的，所以是O(
NlogK)
如果用max-heap的话就是用N大小的堆，建堆需要O(N)的时间，堆顶是最大的值，取K次
，总共是O(KlogN + N)
【在 s********l 的大作中提到】
: 我知道是 max-heap 但是觉得复杂度是 O(NlogK) 不是klogn
|
