问一道面试算法题！

[zeal7s]

有 n 个已排好序的 list 存着 integer ，返回其中出现次数大于 K 的数字，一个 list 中重复的数字只算出现一次，也就是说一个数在 n 个 list 中最多出现 n 次。结果按照出现的次数从小到大排序输出。

我的想法：
1. 遍历所有的数字，将它们放到 HashMap 中， key 是次数， val 是出现的次数。
2. 遍历 Hashmap ，取出次数大于 k 的数，放到 List 中。
3. 最后排序 List ，输出。

感觉自己的解法不是最优的，问下有没有更好的解法？谢谢！

[sumhat]

1. 先对所有的 list 做一遍 unique 操作；
2. 对 list 两两合并直到合并成一个 list ；
3. 对合并之后的 list 扫描一下记数即可；

其中步骤 1 和步骤 2 可以同时完成，但分开做并不影响时间复杂度；
如果 list 是链表，则整个算法不需要额外空间；如果是数组，常规的做法是开辟新的空间来保存合并后的结果，但也有论文研究了如何使用现成的空间做合并： http://www.dcs.kcl.ac.uk/technical-reports/papers/TR-04-05.pdf

[Valyrian]

已经排序好了的不就说明相同的数字都是挨着的吗？
所以不用全存啊，数当前的就可以了

[sumhat]

另一种方法是
1. 在开 n 个指针，分别指向每个 list 的头部
2. 假设 list 从小到大排序，然后用一个最小堆保存所有指针指向的元素数值
3. 如果堆中有数值的个数超过 k ，且没有输出过，就输出这个值
4. 弹出堆顶的值，然后将这个值对应的指针移向它所指 list 的下一个不重复的元素，并把这个值压入堆中
5. 重复 3 和 4 直到所有元素都被遍历过

[mengzhuo]

分析一下就知道你这不是最优的了
要遍历两次 排序一次
其实完全不需要存 hashmap

要计数的都要遍历一次数组 题目中原来排好序的并没有什么用 除非是按次数排的

遍历 元素计数 按次数存数组 排序 返回
O(n) + O(logN) 应该不能更快了吧……

[Cloudee]

因为出现次数不可能>n ，所以可以用桶排序，时间复杂度 O(n)，占的空间也是 O(n)

[mengzhuo]

@Cloudee

桶排在最后需要得到所有非空的元素啊……还得 O(n)一次

[Cloudee]

@mengzhuo 嗯，不过两个 O(n)还是 O(n)，哈哈

[linux40]

用两次红黑树，第一次存数字并计数，第二次按计数存。。。

[linux40]

@linux40 其实用红黑树意味着可以用快排。。。

[linux40]

@linux40 呃，不用快排，请忽视。。

[feiyuanqiu]

都是排好序的可以用归并排序把这 n 个 list 合并成一个 list ，每个 list 重复的相同数字当成一个，然后遍历统计出现最多的数

[Shy07]

1. 每个 list 去重，然后合并成一个 list1
2. 给 list1 排序，然后按相同元素分组，得到 list2
3. 取出 list2 中 size 大于 K 的子 list ，得到 list3
4. 根据子 list 的 size 排序 list3 ，然后打印每个子 list 的首个元素

```ruby
lists = [
[0,1,2,3,4,5,5,5,6,7,7,7,7,7,7],
[1,2,4,5,6],
[3,5,7],
[5,7]
]

K = 2

lists.inject([]) { |mem, list| mem + list.uniq } # 1
.sort.chunk { |x| x }.map(&:last) # 2
.inject([]) { |mem,list| list.size > K ? mem.push(list) : mem } # 3
.sort_by!{ |list| list.size }.each { |list| puts list[0] } # 4
```

不是最优解，但胜在代码量少，实现快

[mengzhuo]

@Cloudee 不过桶排需要元素不重复，貌似要是元素出现次数重复的话……这个就不合适了

[hitmanx]

lz 的解法：
1. 遍历所有的数字，将它们放到 HashMap 中， key 是次数， val 是出现的次数。
2. 遍历 Hashmap ，取出次数大于 k 的数，放到 List 中。
3. 最后排序 List ，输出。

感觉这儿 list 可以是 vector<list>,vector 的大小预留为链表的数量 n 。 vector[x]对应的 list 里存出现次数为 x 的数字。这样最后一步是不用重新排序的。

[RecursiveG]

@mengzhuo 排序不应该是 O(nlogn)么？怎么变 logn 了......
另外 O(n+logn)可以直接写成 O(n)

[zeal7s]

@sumhat 不太明白你的第二个解法。。。
3. 如果堆中有数值的个数超过 k ，且没有输出过，就输出这个值

如何快速地知道堆中某个数值的个数超过 k 呢？赶脚少了什么。。。

[billgreen1]

可不可以这样？对这 n 个列表遍历，计数。计数使用最大 /最小堆，这样遍历完了，堆也建好了。直接返回前面 K 个。

我不懂，瞎说的。

[zeal7s]

@billgreen1 问下，计数使用最大最小堆具体应该怎么做呢？能否详细说明下？

[billgreen1]

参考 wiki 吧，说实话我没写过。 https://en.wikipedia.org/wiki/Min-max_heap

[canesten]

遍历所有数组构造一个 map
map 的 key 是出现次数
map 的 value 是存之前数组元素的 set
再来 k 的时候直接 O(1)解决