← 返回目录

算法笔试模拟题精解之“调整数组”

第 37 / 74 卷日期：

算法笔试模拟题精解之“调整数组”

贡献者 | 陈苇彬

简介：首先理解题意：经过 k 次操作后能出现次数最多的元素 , 以及这个元素的

最小值；然后将示例仔细分析一下，就可以找到解题的方法了。

题目描述

等级：中等

知识点：尺取法

查看题目：调整数组

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 maxValue : 用来存储最大次数所对应的最小值 , 随着最大次数的更新而更

[0]

新 , 初始化为 a

  • int k1 : 用来备份 k 值 , 避免 k 值计算后不见了
  • int temp : 用来统计当前最大数字出现的次数 , 初始化为 arr[i]
  1. 遍历数组 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

[0]

  • 注意 : 当 arr[j] 顺利遍历到 arr时退出循环 , 因为我们的比较最大值操作是在

循环内进行的 , 所以此时 , 可能无法对 max 进行更新 , 因此需要在手动判断一

次 temp 和 max 的大小

  1. 返回数组

时间复杂度 : O（n^2）

空间复杂度 : O（n）

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：调整数组

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”