【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“86.完美排列”的解法探究。先来看一下题目内容：
题目描述
等级：容易
知识点：贪心
查看题目：86.完美排列
完美排列的定义为一个长度为n的数组，n个元素各不相同且每个元素均在[1,n]的范围内。
现在给你长度为n的数组，你每次可以进行如下操作：任选数组中的一个元素，将其加一或者减一，问最少需要多少次操作才能够使得该数组为一个完美排列。
输入一个整数n，表示数组的长度(1 <= n <= 10^4)；
再输入含有n个数的数组，第i个数表示数组中的第i个元素为ai（1 <= ai <= 10^5）。
输出一个整数表示将该数组变成一个完美排列的最少操作次数。
示例1
输入：
2
[3,0]
输出：
2
注意：
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)
看完之后是不是有了答题思路了呢，快来练练手吧：查看题目：完美排列
在线编程周赛、月赛火热进行中，更有限时答题活动，社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程内测中，抢先周赛赢好礼！面试考试前，快来刷刷题！