塔子哥的美食节

问题描述

题解

要求选择 k 个数求出现次数最多的数最大是多少。

根据出现频率排序从小到大排序，并判断当前的数是否能在选中的数作为众数出现。

用一个变量 $t$ 记录已经选择的数字的总和，如果当前数字的频率加上 $t$ 以及剩余数字的最大贡献（即剩余数字个数乘以当前数字的频率）大于等于 $k$，就可以选择当前数字更新答案。

时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。