问一道面试算法题！

[zeal7s]

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

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

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

分析下我的解法的时间复杂度吧：

假设有 m 个 list ，每个 list 有 n 个不同的数。
把所有数字放到 HashMap 中，时间复杂度是 O(m*n)，再遍历一遍 HashMap 挑出合法的数字，时间复杂度仍然不会超过 O(m*n)，假设有 x 个数字满足要求
当 x 较小时，对于输出结果排序，时间复杂度是 O(max(m*n, xlog(x))) ~ O(m*n)
当 x 较大时，极端情况是 x=m*n ，时间复杂度是 O(m*n*log(m*n))

[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)解决

[hitmanx]

@zeal7s heap sort 也是 O(nlgn)的，并不改变排序这一步会改变线性复杂度的事实。

前面的工作都只需要线性复杂度，而最后一步用这种 sort 并不是必须的，因为值域已经锁定了在[0, m]之间，完全可以用类似桶排序的延伸，可以见 14 楼。这样最后一步 sort 也是 O(n)的，总时间复杂度也维持在 O(n)

[Magic347]

这个题，有这么几个需要注意的点吧：
1 ）题中所给的是 n 个有序链表，因此在归并排序时要充分利用这一点，少做无用功
2 ）题中要求了，同一链表内出现的重复数字只能计为 1 次，因此最后的输出结果一定要满足这一条件

那么事实上，主要工作就是怎么对这 n 个有序链表进行归并了，而这一问题还算是一个比较经典的问题，
简而述之，不妨假设有序链表均为升序排列，为此维护一个空间复杂度为 O(n)的最小堆即可。若是假设平均每个链表长度为 m 的话，时间复杂度上也是比较可观的，可以控制在 O(nmlgn)。

初始化时，将 n 个链表的头部元素入堆，此时堆顶即当前 n 个有序链表的最小元素。那么，只要最小堆不空，就不断的弹出堆顶元素输出到归并结果序列。需要注意的是，每次在弹出 1 个堆顶元素时，随即需要入堆 1 个元素，入堆的那个元素即弹出元素所在链表的下一个元素。这一点不难理解，只不过这里就有一个 trick ，为了满足条件 2 ）所要求的，在寻找下一个入堆元素时，若是弹出元素所在链表不空时，要注意略过和弹出元素值相同的那些元素，直到找到第一个与弹出元素值不同的元素入堆。以确保可以维护这一性质，即最小堆堆顶保存的始终是当前 n 个有序链表中最小的那个元素值。

最后，当最小堆中的元素全部出堆，输出得到的序列即归并以后的有序结果序列，而这一序列中也已排除那些因为出现于同一有序链表中而重复计入的元素次数。因为归并后的结果序列已然有序，因此相同元素必定相邻，那么剩下的事就变得简单多了，只要最后遍历一下这个结果序列，时间代价 O(mn)，利用两个变量，一个保存当前元素值，一个作为计数器，便可找到那些出现次数大于 K 的元素。找到以后，把这些元素按照出现次数再排序一番即是原题所求。

综上所述，这种方法的时间代价是 O(nmlgn)，空间代价也较小，控制在 O(n)左右，楼主不妨参考。

[zeal7s]

@Magic347 呃。。。可能是我没说清楚，题目中的 list 我指的是数组，不是链表。

[Magic347]

@zeal7s 数组也无妨，思路是一样的。不过按照以往的经验，一般此类问题多以链表为主，因为对链表查询的好处是可以记录节点指针，这样为了查询出堆元素所在链表的下一个元素只需将指针后移即可。而数组显然做不到这个。

[firefox12]

list 不能 2 分 那么智能从小到大 查询

所有 list 找到 比 k 小的那个数值
然后开始归并




归并的时候 最小值用一个数字记录出现次数， 当出现一个更大的数值就重新记录

然后将结果保存

复杂度 n + n = n

单位时间就能出结果吧

[monkeymonkey]

@hitmanx 支持 14 楼，不用排序的。不过 vector 的大小可以是 n-k 。

具体操作
vector<vector<int>> count;
count[hash[key]-k-1].push_back(hash[key]);
输出的时候二维 vector 转换为一维就可以了。

[monkeymonkey]

打错，应该是 push_back(key)