关于HackerRank《Lily's Homework》：为何交换次数等于N-环数？

首先明确问题核心：
题目中的“beautiful数组”本质就是升序或降序排列的数组——因为所有元素都是不同整数，相邻元素差的绝对值总和最小的情况，必然是元素按大小连续排列（排序后的状态），升序和降序的差总和相等，因此需要分别计算原数组转化为升序、降序数组的最少交换次数，最终取两者的最小值。

接下来重点解释“交换次数=N-环数”的结论：

1. 什么是置换中的“环”？ #

我们把原数组和目标数组（比如升序排序后的数组）做位置映射：对于原数组中的每个元素，找到它在目标数组中应处的位置。这种映射关系可以拆分成若干个环。

举个例子：
原数组：[3, 1, 2]
升序目标数组：[1, 2, 3]
映射关系：

• 原位置0的元素3，应去目标位置2
• 原位置1的元素1，应去目标位置0
• 原位置2的元素2，应去目标位置1
  这就形成了一个环：0 → 2 → 1 → 0（长度为3）。

再比如原数组[4,3,2,1]，升序目标数组[1,2,3,4]：
映射关系：

• 原0的4→目标3；原3的1→目标0 → 环0→3→0（长度2）
• 原1的3→目标2；原2的2→目标1 → 环1→2→1（长度2）
  这里共有2个环。

2. 单个环需要多少次交换？ #

对于长度为k的环：

• 如果k=1：元素已经在正确位置，需要0次交换
• 如果k=2：两个元素互相占了对方的位置，交换1次即可归位（2-1=1）
• 如果k=3：需要2次交换（3-1=2）
• 以此类推，长度为k的环，需要k-1次交换才能让所有元素归位

原因很直接：每次交换最多能让一个元素直接回到正确位置，处理一个k元素的环，需要k-1次交换才能把所有元素都放到目标位置。

3. 总交换次数的推导 #

假设数组总长度为N，所有环的长度分别为k₁, k₂, ..., kₘ（m是环的数量），那么：
所有环的长度之和等于数组长度：k₁ + k₂ + ... + kₘ = N
总交换次数 = 每个环的交换次数之和 = (k₁-1) + (k₂-1) + ... + (kₘ-1)
展开后就是：(k₁+k₂+...+kₘ) - m = N - m

这就是“交换次数=N-环数”的由来。

4. 结合题目场景的实际应用 #

因为题目中的beautiful数组有两种可能（升序和降序），所以需要：

• 第一步：生成升序目标数组，计算原数组到它的环数m₁，得到交换次数N - m₁
• 第二步：生成降序目标数组，计算原数组到它的环数m₂，得到交换次数N - m₂
• 第三步：返回min(N - m₁, N - m₂)，这就是最少交换次数

举个实际例子：
原数组：[2,5,3,1,4]
升序目标数组：[1,2,3,4,5]
映射得到的环：

• 0→1→4→3→0（长度4）
• 2→2（长度1）
  环数m₁=2，交换次数5-2=3

降序目标数组：[5,4,3,2,1]
映射得到的环：

• 0→3→4→1→0（长度4）
• 2→2（长度1）
  环数m₂=2，交换次数5-2=3，因此最小值是3。

总结 #

这个结论的核心是利用置换的环分解特性，每个环的交换次数是环长减一，总和就是数组长度减去环的数量。在《Lily's Homework》中，只需分别计算升序和降序目标的交换次数，取最小即可。

内容的提问来源于stack exchange，提问作者pro na