← 返回目录

算法笔试模拟题精解之“完美排列”

第 13 / 74 卷日期：

算法笔试模拟题精解之“完美排列”

贡献者 | 洪浩原

简介：本文通过两种解法描述 86 题“完美排列”的解题过程，更有对应的时间

和空间复杂度帮助理解。

题目描述

等级：容易

知识点：贪心

查看题目：完美排列

完美排列的定义为一个长度为 n 的数组，n 个元素各不相同且每个元素均在

[1,n] 的范围内。

现在给你长度为 n 的数组，你每次可以进行如下操作：任选数组中的一个元素，

将其加一或者减一，问最少需要多少次操作才能够使得该数组为一个完美排列。

输入一个整数 n，表示数组的长度 (1 <= n <= 10^4)；

再输入含有 n 个数的数组，第 i 个数表示数组中的第 i 个元素为 ai（1 <= ai<= 10^5）。

输出一个整数表示将该数组变成一个完美排列的最少操作次数。

示例 1

输入：

2

[3,0]

输出：

注意：

3->2

0->1

总共需要操作两次。

解法探究

解法一：正常贪心思路

本题是一道典型的贪心算法题，问题可以通过每步的最优策略分治解决。如果将

n 个大小未知的正整数，通过题目中的规则“填充”到槽 1~n 中，我们不妨从最小的

数字槽 1 开始做起。

显然，这 n 个正整数中最小的数字 a（无论这个最小的数字是 1 或是 100），是

填充槽 1 的最佳选择。其它 (n-1) 个数字和 1 的“距离”，都必定大于等于 a，距离

槽 1 的距离都不如 a 更优，所以可以将 a 填充进槽 1，并在后续选择中排除掉它。

当填充槽 2 时，依旧用上面的思路就可以了。用剩下的 (n-1) 个数字中最小的

数字去通过加减 1 进入槽 2，必定是填充槽 2 所有方式中的最佳策略。

将上面的思路重复应用，就得到了结果。复杂度上需要扫描 n 次数组。

时间复杂度：O(n^2)

空间复杂度：O(1)

解法二：排序优化

上面的反复扫描非常浪费时间，不如提前对数组排序，然后从排序后递增数组的

第一项开始，逐个比较与槽 1~n 的距离，最后加到一起，得到答案。

时间复杂度：O(logn)

空间复杂度：O(1)

全站分卷索引 · 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算法笔试模拟题精解之“滑雪比赛”