z*******r
发帖数: 12 | 1 有n个已排好序的list存着integer，返回其中出现次数大于K的数字，一个list中重复
的数字只算出现一次，也就是说一个数在n个list中最多出现n次。结果按照出现的次数
从小到大排序输出。
我的想法：
1. 遍历所有的数字，将它们放到HashMap中，key是次数，val是出现的次数。
2. 遍历Hashmap，取出次数大于k的数，放到List中。
3. 最后排序List，输出。
感觉自己的解法不是最优的，问下有没有更好的解法？谢谢！ |
r******8
发帖数: 1486 | 2 反正都排好序了，为什么不一边算频率，一边放minheap/maxheap里面，最后打出K个就
好了。。
。 |
d**********6
发帖数: 58 | 3 我感觉排序了的这个用不上呀，麻烦详细说说？
【在 r******8 的大作中提到】
: 反正都排好序了，为什么不一边算频率，一边放minheap/maxheap里面，最后打出K个就
: 好了。。
: 。
|
r***e
发帖数: 213 | 4 频率最大是n，就用n长的数组，存freq是i的number list， java的话是List
Integer>>
给的list是有序的，过一遍可以得到所有数字的频率，然后就是i from k to n-1的
freq num list |
n****5
发帖数: 81 | 5 robert88说的应该是比较好的办法，基本上就是“merge k sorted list” 的变形（升
级）。 |
d**********6
发帖数: 58 | 6 傻傻问一下，去除每个list内部的重复，难道不用个set之类的东西？ |
z****c
发帖数: 3 | 7 就是求doc freq吧，然后输出大于K的，把一个list看成一个document的话。项目中写
过n次，只会暴力过一遍，不知道如何优化。 |
j******o
发帖数: 4219 | 8 我的想法是先用set把list中重复的去掉，然后merge k sorted list，最后用
Collections的count（） |
z*******r
发帖数: 12 | 9 假设有m个list，每个list有n个数，同时假设每个list中没有重复的数字。
对于merge k sorted list那种方法来说，首先用priorityqueue merge，同时poll出来
数字时统计相同的数字有多少个。所以每个数字都要进队列一次，出队列一次，
priorityqueue中只能同时有m个数字。所以这部分时间复杂度是O(m*n*log(m))。
接着为了保证输出有序，对符合要求的数字排序，假设有x数字满足要求，时间复杂度
是O(xlog(x))
如果x不是很大，那么这种方法的时间复杂度应该是O(max(m*n*log(m), xlog(x))) ~ O
(m*n*log(m))
对于楼主方法来说，把所有数字放到HashMap中，时间复杂度是O(m*n)，再遍历一遍
HashMap挑出合法的数字，时间复杂度仍然不会超过O(m*n)
对于输出结果排序，时间复杂度是O(max(m*n, xlog(x))) ~ O(m*n)
对于最坏情况来说，每个数字都要输出，那么x=m*n，时间复杂度是O(m*nlog(m*n))
从时间复杂度的角度来说楼主的方法应该是要优于merge k sorted list那种方法，从
空间复杂度角度来说，应该是merge k sorted list那种方法更好。
我的分析应该是正确的吧？ |
d********y
发帖数: 2114 | 10 找到最小值中的最小值，计算频率
频率大于k的保留
list当前值等于最小值的指针后移到大于这个最小值的位置
重复以上到所有list结束
对保留的结果排序输出
【在 z*******r 的大作中提到】
: 有n个已排好序的list存着integer，返回其中出现次数大于K的数字，一个list中重复
: 的数字只算出现一次，也就是说一个数在n个list中最多出现n次。结果按照出现的次数
: 从小到大排序输出。
: 我的想法：
: 1. 遍历所有的数字，将它们放到HashMap中，key是次数，val是出现的次数。
: 2. 遍历Hashmap，取出次数大于k的数，放到List中。
: 3. 最后排序List，输出。
: 感觉自己的解法不是最优的，问下有没有更好的解法？谢谢！
|
I******c
发帖数: 163 | 11 综合了一些大伙的意见
1.类似于merge k sorted list， 使用了一个minheap, 每次出一个最小的数值，然后
从同一个list里补充一个(同时把list里相同的数都省略掉）
2.每次出的数值和上次出的相同，就在频率上加一，如果不同，就把上次数值的频率存
起来（如果大于k)。riple的存储方法可行。
3. 最后输出结果。
时间复杂度 total*lg(n). total是数的总数。n是list的个数。 |
