第1题-塔子哥的美食节 - Problem Detail - CodeFun2000

ID: 924

Difficulty: 3

所属公司 : 阿里

时间 :2024年4月10日-阿里淘天

小红的美食节

问题描述

题解

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

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

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

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