2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复
比如,arr = [4, 2, 0, 3, 1]
0 1 2 3 4
把0想象成洞...,并且走后留下洞
通过搬家的方式,想变成有序的,有序有两种形式
比如arr = [4, 2, 0, 3, 1],变成
[0, 1, 2, 3, 4]或者[1, 2, 3, 4, 0]都叫有序。...对于第二种有序情况,我们可以先倒序遍历数组,找出每个数需要移动的最小距离,从而计算出需要移动的次数。
3. 最后比较这两种情况下的最小搬动次数,返回较小值即可。
注意事项:
1....需要记录每个数是否被遍历过,以防止重复计算。
2. 数字只能搬家到洞里,并且走后留下洞,因此在交换过程中需要记录其中一个数字所在的位置作为洞的位置。...这种样子,至少交换几次
// ans2 : 1 2 3 4 .... 0 这种样子,至少交换几次
// m : 每个环里有几个数
// next : 往下跳的位置
n := len(nums