遇到一个完美排列问题，求解答。
完美排列的定义为一个长度为n的数组，n个元素各不相同且每个元素均在[1,n] 的范围内。现在给你长度为n的数组，你每次可以进行如下操作:任选数组中的一个元素，将其加一或者减一，问最少需要多少次操作才能够使得该数组为一个完美排列。输入一个整数 n，表示数组的长度 (1 <=n<=10^4)；再输入含有n个数的数组，第i个数表示数组中的第i个元素为ai（1<=ai<=10^5）。输出一个整数表示将该数组变成一个完美排列的最少操作次数。
展开
收起
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次数组。 输入：2 [3,0] 输出：2 3->2 0->1 总共需要操作两次。
2021-12-23 18:28:24赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
