问一道面试算法题！

[zeal7s]

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

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

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

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