在线编程介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding
本文为大家介绍其中的 第89题：调整数组 的题目解析，具体如下：
题目描述
等级：中等
知识点：尺取法
查看题目：调整数组
A同学有一个长度为n的数组，对于这个数组，他能够进行k次如下操作：任选数组中的某个元素将其数值加一（一个元素可以被加多次）。
他想在操作不超过k次的情况下，使得数组中某一元素的出现次数尽可能的多，并同时使这个元素尽可能的小。
请你找出出现次数最多的元素的出现次数以及此时这个元素的最小值。
输入:
输入数组长度n(1 <= n <= 10^5)，最多能操作次数k(1 <= k <= 10^5)，和一个包含n个数的数组，数组中第i个元素的值为ai(0 <= ai <= 10^4)。
输出:
输出操作后出现次数最多的元素的出现次数以及此时这个元素的最小值。
解题方法：模拟法
变量概述
- int n : 有n个数
- int k : 最多操作k次
- int[] a : 存储n个数的数组
- 只能对a[i]进行一种操作 : +1
首先理解题意：经过k次操作后能出现次数最多的元素, 以及这个元素的最小值；
示例说明：
- 1 2 2 3 3 4
两个3要变成4就得操作2次
两个2要变成4就得操作4次
- 因为 ai 的大小被限定在[0, 10^4], 所以可以使用一个数组arr, 来统计每个数字出现的次数。
- 遍历数组arr, 对于任意不等于0的数arr[i], 逆向遍历前面所有
*不为0的***arr[j]**, 并对每个不为0的arr[j],**k-=arr[j] * (i-j)**, 直到k不够减或没前面没数字了。 - 如果是k不够减, 则得在判断k能够再减去多少个arr[j], 因为之前的公式是计算减去所有的arr[j]的
- 之所以要不为0的, 是因为压根没有这个数, 无法对其进行+操作
解题步骤
1、定义变量
- int[] arr : 用来存储每个数字出现的次数, 容量为10001
- int max : 用来存储最大次数, 初始化为1
- int maxValue : 用来存储最大次数所对应的最小值, 随着最大次数的更新而更新, 初始化为a[0]
- int k1 : 用来备份k值, 避免k值计算后不见了
- int temp : 用来统计当前最大数字出现的次数, 初始化为arr[i]
2、遍历数组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的大小
3、返回数组
时间复杂度: O（n^2）
空间复杂度: O（n）
看完之后是不是有了想法了呢，快来练练手吧>>查看题目：调整数组
