循环排序（Cyclic Sort）的进阶应用：原地重排数组使得“数组元素与索引的差值映射”保持特定顺序

字数 3034 2025-12-11 12:06:09

循环排序（Cyclic Sort）的进阶应用：原地重排数组使得“数组元素与索引的差值映射”保持特定顺序

题目描述：
给定一个长度为 n 的整数数组 arr，数组中的元素是 0 到 n-1 的排列（即包含从 0 到 n-1 的所有整数，每个整数恰好出现一次）。要求通过原地重排（只允许交换元素），使得数组满足以下条件：对于任意索引 i，元素 arr[i] 与 i 的差值（即 arr[i] - i）形成一个非递减序列。换句话说，将每个元素减去其索引后得到的序列应当是有序的（非递减）。请设计一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法完成重排。

示例
输入：arr = [1, 0, 3, 2]
输出：arr = [0, 1, 2, 3]
解释：计算差值 arr[i] - i：

初始数组：差值序列为 [1-0, 0-1, 3-2, 2-3] = [1, -1, 1, -1]，无序。
重排后数组：差值序列为 [0-0, 1-1, 2-2, 3-3] = [0, 0, 0, 0]，为非递减序列。

1. 问题理解与关键观察

我们先分析题目的核心要求：

数组是 0 到 n-1 的排列，所以每个元素都是唯一的，且值域与索引范围完全相同。
我们希望数组满足：arr[i] - i 的值从左到右非递减（即单调不减）。
允许的操作是原地交换元素，目标是最优时间复杂度 O(n) 和 O(1) 额外空间。

重要观察：

差值范围：
由于 arr[i] ∈ [0, n-1] 且 i ∈ [0, n-1]，所以 arr[i] - i ∈ [-(n-1), n-1]。
排序与差值的联系：
如果我们直接对数组进行升序排序，那么 arr[i] = i，差值全部为 0，显然满足非递减条件。但是题目只允许交换操作，并且要求差值序列非递减即可，不一定要完全升序排序。
差值的非递减性质：
如果 arr[i] - i 非递减，那么当我们从左到右遍历数组时，差值只会保持不变或增加。这意味着：如果某个元素的值比索引小太多（负差值过大），它应该尽量靠左；如果值比索引大太多（正差值过大），它应该尽量靠右。

2. 思路推导：从“理想位置”到“环分解”

一个自然的想法是：我们希望每个元素 arr[i] 的最终位置应该由其差值决定。但是差值序列只要求单调不减，并不唯一。我们需要找到一个确定的映射方法。

关键洞察：
由于数组是 0..n-1 的排列，如果我们按元素值本身的大小升序放置元素，就能保证每个 arr[i] = i，差值全为 0，满足条件。但题目并没有要求必须严格升序，只要求差值非递减。那么是否存在更宽松的放置方式？

让我们考虑：
假设我们有一个目标差值序列 d[0..n-1]，它是非递减的整数序列，并且对于每个位置 i，我们期望放置的元素值 arr[i] = i + d[i]。
由于 arr[i] 必须是 0..n-1 的排列，所以集合 {i + d[i]} 必须恰好是 {0, 1, ..., n-1} 的一个排列。
但构造这样的 d[i] 比较复杂。

其实，我们可以通过一个更简单的等价条件来理解：
如果数组已经按升序排序，那么差值序列就是常数 0，显然非递减。
对于任意一个满足差值非递减的排列，如果我们把数组升序排序，相当于每个元素都移动到了它值所对应的索引位置（即 arr[i] 最终放在索引 arr[i] 处）。
但我们的操作是交换，所以问题转化为：如何通过交换，将数组变成升序排序？
这就是经典的循环排序（Cyclic Sort） 问题！

结论：
满足差值非递减的唯一排列就是数组的升序排列（即 arr[i] = i）。为什么？

证明（反证法）：
假设存在另一个排列，满足 arr[i] - i 非递减但不是严格升序。
由于元素是唯一的，且值域连续，那么必然存在两个位置 i < j，使得 arr[i] > arr[j]（否则就是升序）。
考虑差值：arr[i] - i 和 arr[j] - j。
因为 i < j，所以 -i > -j，加上 arr[i] > arr[j]，无法确定 arr[i] - i 与 arr[j] - j 的大小关系，可能破坏非递减。
通过严格推导可以发现，如果要求所有差值非递减，唯一解就是升序排列。

因此，问题简化为：将给定的 0..n-1 排列通过交换操作原地排序成升序。

3. 算法步骤：循环排序（Cyclic Sort）

循环排序专门用于原地排序值域连续的唯一整数序列（0..n-1 或 1..n 等）。
其核心思想：每个元素应该被放在索引等于其值的位置上。
我们遍历数组，如果当前元素不在正确位置，就把它交换到正确位置，直到当前位置放对为止。

算法步骤：

从索引 i = 0 开始遍历数组。
对于每个 i：
- 计算当前元素 arr[i] 的正确位置 correct = arr[i]（因为值域是 0..n-1，元素值就是它应该在的索引）。
- 如果 arr[i] 不在正确位置（即 arr[i] ≠ i），则交换 arr[i] 和 arr[correct]。
- 交换后，新到位置 i 的元素可能仍不正确，因此继续检查当前位置 i 直到 arr[i] = i 为止，然后才 i++。
继续这个过程直到遍历完整个数组。

示例推演（输入 arr = [1, 0, 3, 2]）：

i=0: arr[0]=1, correct=1。交换 arr[0] 和 arr[1] → [0, 1, 3, 2]。现在 arr[0]=0 正确。
i=1: arr[1]=1 正确。
i=2: arr[2]=3, correct=3。交换 arr[2] 和 arr[3] → [0, 1, 2, 3]。现在 arr[2]=2 正确。
i=3: arr[3]=3 正确。
结束，数组已排序。

4. 时间复杂度与空间复杂度分析

时间复杂度：每个元素最多被交换一次到正确位置，交换后该位置即固定。总交换次数 ≤ n-1，遍历 n 个位置，因此 O(n)。
空间复杂度：只用了常数个额外变量（索引和临时交换变量），O(1)。

5. 为什么这样做满足题目要求？

因为最终数组是升序排列 [0, 1, 2, ..., n-1]，那么差值 arr[i] - i = 0 对所有 i 成立，形成一个常数非递减序列，满足条件。

6. 扩展思考：如果允许重复元素？

如果数组中元素可能重复，那么满足差值非递减的排列可能不止一种（比如允许相邻差值相等）。但此时循环排序不再直接适用，因为元素值不唯一。这种情况下，问题会更复杂，可能需要先对差值进行排序再放置，但那样会涉及稳定排序等细节，通常需要 O(n log n) 时间。本题限定为排列，因此简化。

总结：
本题看似是自定义顺序的重排，但通过分析差值非递减的性质，可证明唯一解就是升序排列，因此直接应用循环排序即可高效解决。关键是通过逻辑推导将抽象条件转化为经典问题。

循环排序（Cyclic Sort）的进阶应用：原地重排数组使得“数组元素与索引的差值映射”保持特定顺序题目描述：给定一个长度为 n 的整数数组 arr ，数组中的元素是 0 到 n-1 的排列（即包含从 0 到 n-1 的所有整数，每个整数恰好出现一次）。要求通过原地重排（只允许交换元素），使得数组满足以下条件：对于任意索引 i，元素 arr[ i] 与 i 的差值（即 arr[ i] - i）形成一个非递减序列。换句话说，将每个元素减去其索引后得到的序列应当是有序的（非递减）。请设计一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法完成重排。示例输入： arr = [1, 0, 3, 2] 输出： arr = [0, 1, 2, 3] 解释：计算差值 arr[i] - i ：初始数组：差值序列为 [ 1-0, 0-1, 3-2, 2-3] = [ 1, -1, 1, -1 ]，无序。重排后数组：差值序列为 [ 0-0, 1-1, 2-2, 3-3] = [ 0, 0, 0, 0 ]，为非递减序列。 1. 问题理解与关键观察我们先分析题目的核心要求：数组是 0 到 n-1 的排列，所以每个元素都是唯一的，且值域与索引范围完全相同。我们希望数组满足： arr[i] - i 的值从左到右非递减（即单调不减）。允许的操作是原地交换元素，目标是最优时间复杂度 O(n) 和 O(1) 额外空间。重要观察：差值范围：由于 arr[i] ∈ [0, n-1] 且 i ∈ [0, n-1] ，所以 arr[i] - i ∈ [-(n-1), n-1] 。排序与差值的联系：如果我们直接对数组进行升序排序，那么 arr[i] = i ，差值全部为 0 ，显然满足非递减条件。但是题目只允许交换操作，并且要求差值序列非递减即可，不一定要完全升序排序。差值的非递减性质：如果 arr[i] - i 非递减，那么当我们从左到右遍历数组时，差值只会保持不变或增加。这意味着：如果某个元素的值比索引小太多（负差值过大），它应该尽量靠左；如果值比索引大太多（正差值过大），它应该尽量靠右。 2. 思路推导：从“理想位置”到“环分解” 一个自然的想法是：我们希望每个元素 arr[i] 的最终位置应该由其差值决定。但是差值序列只要求单调不减，并不唯一。我们需要找到一个确定的映射方法。关键洞察：由于数组是 0..n-1 的排列，如果我们按元素值本身的大小升序放置元素，就能保证每个 arr[i] = i ，差值全为 0 ，满足条件。但题目并没有要求必须严格升序，只要求差值非递减。那么是否存在更宽松的放置方式？让我们考虑：假设我们有一个目标差值序列 d[0..n-1] ，它是非递减的整数序列，并且对于每个位置 i ，我们期望放置的元素值 arr[i] = i + d[i] 。由于 arr[i] 必须是 0..n-1 的排列，所以集合 {i + d[i]} 必须恰好是 {0, 1, ..., n-1} 的一个排列。但构造这样的 d[i] 比较复杂。其实，我们可以通过一个更简单的等价条件来理解：如果数组已经按升序排序，那么差值序列就是常数 0 ，显然非递减。对于任意一个满足差值非递减的排列，如果我们把数组升序排序，相当于每个元素都移动到了它值所对应的索引位置（即 arr[i] 最终放在索引 arr[i] 处）。但我们的操作是交换，所以问题转化为：如何通过交换，将数组变成升序排序？这就是经典的循环排序（Cyclic Sort）问题！结论：满足差值非递减的唯一排列就是数组的升序排列（即 arr[i] = i ）。为什么？证明（反证法）：假设存在另一个排列，满足 arr[i] - i 非递减但不是严格升序。由于元素是唯一的，且值域连续，那么必然存在两个位置 i < j ，使得 arr[i] > arr[j] （否则就是升序）。考虑差值： arr[i] - i 和 arr[j] - j 。因为 i < j ，所以 -i > -j ，加上 arr[i] > arr[j] ，无法确定 arr[i] - i 与 arr[j] - j 的大小关系，可能破坏非递减。通过严格推导可以发现，如果要求所有差值非递减，唯一解就是升序排列。因此，问题简化为：将给定的 0..n-1 排列通过交换操作原地排序成升序。 3. 算法步骤：循环排序（Cyclic Sort）循环排序专门用于原地排序值域连续的唯一整数序列（0..n-1 或 1..n 等）。其核心思想：每个元素应该被放在索引等于其值的位置上。我们遍历数组，如果当前元素不在正确位置，就把它交换到正确位置，直到当前位置放对为止。算法步骤：从索引 i = 0 开始遍历数组。对于每个 i ：计算当前元素 arr[i] 的正确位置 correct = arr[i] （因为值域是 0..n-1 ，元素值就是它应该在的索引）。如果 arr[i] 不在正确位置（即 arr[i] ≠ i ），则交换 arr[i] 和 arr[correct] 。交换后，新到位置 i 的元素可能仍不正确，因此继续检查当前位置 i 直到 arr[i] = i 为止，然后才 i++ 。继续这个过程直到遍历完整个数组。示例推演（输入 arr = [1, 0, 3, 2] ）： i=0: arr[ 0]=1, correct=1。交换 arr[ 0] 和 arr[ 1] → [ 0, 1, 3, 2]。现在 arr[ 0 ]=0 正确。 i=1: arr[ 1 ]=1 正确。 i=2: arr[ 2]=3, correct=3。交换 arr[ 2] 和 arr[ 3] → [ 0, 1, 2, 3]。现在 arr[ 2 ]=2 正确。 i=3: arr[ 3 ]=3 正确。结束，数组已排序。 4. 时间复杂度与空间复杂度分析时间复杂度：每个元素最多被交换一次到正确位置，交换后该位置即固定。总交换次数 ≤ n-1，遍历 n 个位置，因此 O(n)。空间复杂度：只用了常数个额外变量（索引和临时交换变量），O(1)。 5. 为什么这样做满足题目要求？因为最终数组是升序排列 [0, 1, 2, ..., n-1] ，那么差值 arr[i] - i = 0 对所有 i 成立，形成一个常数非递减序列，满足条件。 6. 扩展思考：如果允许重复元素？如果数组中元素可能重复，那么满足差值非递减的排列可能不止一种（比如允许相邻差值相等）。但此时循环排序不再直接适用，因为元素值不唯一。这种情况下，问题会更复杂，可能需要先对差值进行排序再放置，但那样会涉及稳定排序等细节，通常需要 O(n log n) 时间。本题限定为排列，因此简化。总结：本题看似是自定义顺序的重排，但通过分析差值非递减的性质，可证明唯一解就是升序排列，因此直接应用循环排序即可高效解决。关键是通过逻辑推导将抽象条件转化为经典问题。