86.完美排列

题目概述

题目详情(点我)

完美排列的定义为一个长度为n的数组，n个元素各不相同且每个元素均在[1,n]的范围内。
现在给你长度为n的数组，你每次可以进行如下操作：任选数组中的一个元素，将其加一或者减一，问最少需要多少次操作才能够使得该数组为一个完美排列。

输入:
输入一个整数n，表示数组的长度(1 <= n <= 10^4)；
再输入含有n个数的数组，第i个数表示数组中的第i个元素为ai（1 <= ai <= 10^5）。

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

题解

解题方法

• 排序

算法知识

• 贪心

  • 时间复杂度: n^2
  • 空间复杂度: 1

解题思路

审题:

a : 数组
n : 数组长度
result : 结果, 初始值为0

目标: n个元素各不相同且均在[1,n]内

原理:

• 因为题目要求结果在数字均在[1,n]这个范围内。所以我们将数组a内的数字进行从小到大排序。
• 让a[0]变成1, a[1]变成2, …, a[n-1]变成n
  分别需要操作a[0]-(0+1)次，a[1]-(1+1)次, a[n-1]-(n-1+1)次
• 贪心算法体现在: 让最小的值变成要求范围内最小的值, 从而得到最小的操作次数

解题步骤:

1. 对数组a进行从小到大排序
2. 然后对数组a进行遍历, 记录第i个元素的值与i+1 ( i ∈ [0, n-1] ) 的差的绝对值temp, 并将temp累加到result中
3. 返回result