遇到一个调整数组的问题，求解答。
A 同学有一个长度为 n 的数组，对于这个数组，他能够进行 k 次如下操作：任选数组中的某个元素将其数值加一（一个元素可以被加多次）。他想在操作不超过 k 次的情况下，使得数组中某一元素的出现次数尽可能的多，并同时使这个元素尽可能的小。请你找出出现次数最多的元素的出现次数以及此时这个元素的最小值。
展开
收起
1
条回答
写回答
写回答
-
- 定义变量 ● int[] arr :用来存储每个数字出现的次数 , 容量为 10001 ● int max :用来存储最大次数 ,初始化为 1 ● int maxValue:用来存储最大次数所对应的最小值 ,随着最大次数的更新而更新，初始化为 a[0] ● int k1: 用来备份 k 值 , 避免 k 值计算后不见了 ● int temp:用来统计当前最大数字出现的次数 ,初始化为 arr[i]
- 遍历数组 arr, 找出出现最多的次数以及对应的最小值 . ● 对于每个 arr[j] 如果 arr[j] 为 0, 则直接跳过 . 不是不加，而是没法加 ● 如果 arr[j] *(i-j) <=k,证明当前的操作次数能够将 j 全部变成 i,则使用 temp加上所有的 j ● 如果 arr[j] *(i-j) >k,则证明当前次数k无法将全部j变成 i，开始尝试将部分j 转成 i ○ 使用 k/(i-j) 计算还能够将多少个 j 转成 i，然后进行转换 ○ 判断temp和最大值是否大于最大次数max,如果大于,则更新max和maxValue ● 注意 :当 arr[j] 顺利遍历到 arr[0] 时退出循环,因为我们的比较最大值操作是在循环内进行的 ,所以此时,可能无法对 max 进行更新,因此需要在手动判断一次 temp和 max 的大小
- 返回数组 因此输入 :输入数组长度 n(1<= n<= 10^5)，最多能操作次数 k(1<= k<= 10^5)，和一个包含 n 个数的数组，数组中第i个元素的值为ai(0<=ai<=10^4)。 输出 :输出操作后出现次数最多的元素的出现次数以及此时这个元素的最小值.
2021-12-23 18:44:42赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
