g5-08231. 词频前 k · 林老师的题库

题目描述

读入 $n$ 个整数（值都在 $1$ 到 $1 0^{6}$ 之间），统计每个值出现的次数，输出出现次数最多的 $k$ 个值：按次数从多到少排；次数相同的，值小的在前。每行输出「值次数」（空格分隔）。数据保证不同值的个数至少为 $k$ 。

做法：先用数组按值计数，再把每个出现过的值编码进大根堆——次数乘 $1 0^{6}$ 放高位，低位放 $1 0^{6}$ 减去值：次数相同时，值小的编码反而大，先弹出的就是它。

第一行两个整数 $n$ 、 $k$ （ $1 \leq k \leq n \leq 2 \times 1 0^{5}$ ）。

第二行 $n$ 个整数 $a_{i}$ （ $1 \leq a_{i} \leq 1 0^{6}$ ）。

共 $k$ 行，每行两个整数「值次数」，按次数从多到少、同次数值从小到大排列。

输入：

7 3
4 4 2 2 2 9 9

输出：

2 3
4 2
9 2

2 出现 3 次最多；4 和 9 都出现 2 次，值小的 4 排前。

$1 \leq k \leq n \leq 2 \times 1 0^{5}$ ， $1 \leq a_{i} \leq 1 0^{6}$ 。提示：编码低位放 $1 0^{6} -$ 值还是放值，决定同次数时谁先弹出——方向写反，平局全错。