LeetCode 补充题 15. 自然数数组的排序

约 9 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 腾讯 高频面试题
标签
数组
目录

题目描述

✅ 补充题 15. 自然数数组的排序

题意分析

给定长度为 n 的数组，里面恰好是 1 到 n 这 n 个互不相等的自然数，只是顺序被打乱了，要求把它排好序。

真正定义这道题的是两条硬性指标：时间 $O(n)$、额外空间 $O(1)$。前者直接封死了所有基于比较的排序——比较排序的下界就是 $O(n \log n)$；后者又封死了开一个计数数组或结果数组回填的做法，那是 $O(n)$ 额外空间。两条一起看，只剩下「在原数组上就地搬运」这一条路。

输入的特殊性正是可以利用的信号：值域与下标一一对应。数组里存的不是任意整数，而是恰好 1..n 的一个排列，于是每个值都自带它最终该待的位置——值 v 属于下标 v - 1。排好序的数组等价于「每个位置放着下标加一」。题目里「互不相等」这四个字保证了这个对应是双射，不会出现两个值抢同一个位置。

边界：长度为 0 或 1 时天然有序，直接返回；已经有序的输入应当一次交换都不做，实现要能自然满足这一点而不是靠特判。

解法：值归位的原地交换

核心思路

暴力做法是直接调库排序，$O(n \log n)$；稍微利用一点值域信息就是计数排序，扫一遍统计出现次数再从小到大回填，时间降到 $O(n)$。但计数排序需要一个长度为 n 的计数数组，额外空间 $O(n)$，卡在题目的空间线上。瓶颈在于：它用一块新内存来记录「哪个值该出现几次」，可这份信息在本题中根本不需要记——每个值只出现一次，且位置由值本身唯一决定。

观察由此而来：既然值 v 只能待在下标 v - 1，那么当我在下标 i 上看到一个不等于 i + 1 的值时，我完全知道它该去哪里；而把它送过去时被挤走的那个值，同样带着自己的目的地。于是「排序」退化成了「把每个值送回家」，全程只需要交换，不需要任何额外容器。

具体做法：外层下标 i 从左到右走一遍，内层用 while (arr[i] != i + 1) 反复把 arr[i] 换到它的目标位 arr[i] - 1 上，直到下标 i 上摆的正是 i + 1。

不变量：外层每次进入下标 i 之前，[0, i) 区间内的每个位置 j 都已满足 arr[j] == j + 1，并且此后永不改变。 后半句是关键：内层交换的目标位 arr[i] - 1 绝不会落进 [0, i)，因为那些位置上的值已经等于自己的下标加一，若目标位是它们，说明 arr[i] 与那里的值相等，与「互不相等」矛盾。所以已归位的前缀不会被破坏，外层走完一遍整个数组就有序了。

循环次数也由这条不变量兜住：内层每做一次交换，至少有一个值被永久放到正确位置上，而全数组只有 n 个值，因此所有内层交换加起来最多 n 次。外层 n 次判断加上总计不超过 n 次交换，整体就是 $O(n)$，而不是看到嵌套循环就以为的 $O(n^2)$。

解题步骤

  • 先挡掉长度小于 2 的输入：不是为了正确性（空数组与单元素数组走主逻辑也不会出错），而是让「无需处理」这件事在代码里表达出来。
  • 外层 for i 从 0 遍历到 n-1：i 的语义是「当前要保证归位的位置」，不是「当前要处理的元素」。这个区分很重要，因为位置 i 上的元素在内层循环中会被换掉好几茬。
  • 内层写成 while 而不是 if：一次交换换进来的新值通常也不属于位置 i，必须继续换，直到 arr[i] == i + 1 才罢手。写成 if 就只搬一次，剩下的错位元素被跳过。
  • 循环条件用 arr[i] != i + 1 而不是「换过来的值是否有序」：这个条件同时充当了终止判据和归位判据，已经在正确位置的元素一次交换都不会做，天然满足「已排好序的输入零交换」。
  • 交换时先把目标下标算进临时变量 target = arr[i] - 1：arr[i] 在交换过程中会被改写，若在赋值语句中间再取一次 arr[i]，读到的已经是新值，会把数据换乱。Go 里用 arr[i], arr[t] = arr[t], arr[i] 是安全的，因为右侧先整体求值。

以 [3, 2, 1, 5, 4] 走一遍。

i = 0：arr[0] = 3 != 1，目标位 3 - 1 = 2，交换 0 与 2，得 [1, 2, 3, 5, 4]；再判断 arr[0] = 1 == 1，内层退出，位置 0 归位。
i = 1：arr[1] = 2 == 2，一次交换都不做。
i = 2：arr[2] = 3 == 3，同样不动——它是刚才那次交换顺手送回家的。
i = 3：arr[3] = 5 != 4，目标位 5 - 1 = 4，交换 3 与 4，得 [1, 2, 3, 4, 5]；再判断 arr[3] = 4 == 4，退出。
i = 4：arr[4] = 5 == 5，不动。

全程只做了 2 次交换，结果 [1, 2, 3, 4, 5]。注意 i = 0 那一次交换同时让位置 0 和位置 2 都归了位，这正是「总交换次数不超过 n」的直观来源。

while 不能换成 if。反例 [2, 3, 4, 5, 1]：每个下标只交换一次后，数组依次变为 [3, 2, 4, 5, 1]、[3, 2, 5, 4, 1]、[1, 2, 5, 4, 3]，循环结束仍未有序。一次交换只能保证被送走的值归位，换到当前位置的新值可能仍然错位，所以必须在同一个 i 上继续处理。

代码实现

// 值 v 的归宿是下标 v - 1，反复把当前位置的值送回家直到它归位。
class Solution {
    public int[] sortArray(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }

        for (int i = 0; i < arr.length; i++) {
            while (arr[i] != i + 1) {
                // 先固定目标下标，避免交换过程中 arr[i] 被改写后再取值。
                int target = arr[i] - 1;
                int tmp = arr[target];
                arr[target] = arr[i];
                arr[i] = tmp;
            }
        }

        return arr;
    }
}

// 值 v 的归宿是下标 v - 1，反复把当前位置的值送回家直到它归位。
func sortArray(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}

	for i := 0; i < len(arr); i++ {
		for arr[i] != i+1 {
			// 右侧先整体求值，交换是安全的。
			t := arr[i] - 1
			arr[i], arr[t] = arr[t], arr[i]
		}
	}

	return arr
}

复杂度分析

  • 时间复杂度：$O(n)$，凭的是每次交换都至少让一个值永久落到正确位置，全数组只有 n 个值，所以内层交换总次数不超过 n；外层的 n 次判断与之相加仍是线性，嵌套循环并不意味着平方。
  • 空间复杂度：$O(1)$，凭的是全程只用了 i、target、tmp 三个下标或值变量，没有申请任何与 n 相关的容器，排序完全发生在原数组上。

关键点总结

  • 当值域与下标存在一一对应时，「排序」可以退化成「归位」，这是绕开比较排序 $O(n \log n)$ 下界的标准手法，也是本题唯一想考的东西。
  • 嵌套循环的复杂度要用势能 / 摊还的角度算：找出一个单调变化且有上界的量（这里是「已归位元素个数」），用它去数总操作次数，而不是简单地把内外层次数相乘。面试中被问「这不是 $O(n^2)$ 吗」，这段话就是标准答案。
  • 原地算法的正确性靠不变量加上「已完成前缀不会被破坏」两条一起证。本题中后者依赖「元素互不相等」，题目一旦改成允许重复，这套写法就要改成 41、442 那类带额外判等的版本。
  • 循环条件直接写成「目标状态是否达成」（arr[i] != i + 1），比写成「换了几次」更不容易错，也顺带让有序输入零开销。
  • 面试视角：面试官抛出「$O(n)$ 时间、$O(1)$ 空间」这种组合限制时，先复述限制封死了哪些常规解法，再指出输入的哪条特殊性质可以补上这个缺口。这个推理过程比直接写出交换代码更值分。

易错点总结

  • 错误写法：内层用 if 而不是 while：[2, 3, 4, 5, 1] 每个下标只换一次后会得到 [1, 2, 5, 4, 3]，并未有序。换进 arr[i] 的新值还可能需要继续归位。
  • 错误写法：目标下标写成 arr[i] 而不是 arr[i] - 1：[2, 1] → 目标位算成 2，直接数组越界抛异常；即使不越界也整体错开一位。
  • 错误写法：交换过程中再次用已经改写的 arr[i] 计算目标位。例如先执行 arr[i] = arr[arr[i] - 1]，再用新的 arr[i] - 1 写回旧值，会写到另一个位置；[3, 2, 1] 甚至会原地打转。应像代码一样先固定 target，再完成交换。
  • 错误写法：把题目的排列保证忽略掉，直接复用到含重复或越界值的数组：[1, 1] 在 i = 1 时会不断交换两个 1，形成死循环；值为 0 或大于 n 时会越界。若输入不再保证是 1..n 的排列，必须先校验或改用允许重复值的归位模板。
  • 错误写法：为了「保险」额外开一个 int[] res 回填：[3, 2, 1] 结果虽然正确，但额外空间变成 $O(n)$，直接违反题目限制——这道题的全部考点就在空间上，答对结果等于没答。
  • 错误写法：直接调用库排序：[3, 2, 1] 结果正确，但时间是 $O(n \log n)$，且完全没有用到「值是 1..n 的排列」这条给定条件，面试中会被判定为没读懂题。
  • 错误写法：归位条件写成 arr[i] != i：本题值从 1 开始、下标从 0 开始；[1] 会被误判为错位，并反复与自己交换。目标状态必须是 arr[i] == i + 1。
  • 错误写法：以为已排好序的输入也要 O(n) 次交换而提前特判 isSorted：[1, 2, 3, 4] → 多一次 $O(n)$ 扫描却毫无收益，主循环本身在有序输入下就是零交换，特判是纯粹的冗余代码。

相似题目

题目 难度 考察点
41. 缺失的第一个正数 困难 同样是值归位，但值域不再是完美排列，要额外过滤越界值与重复值，归位后再扫一遍找第一个错位
442. 数组中重复的数据 中等 允许出现两次，归位失败的位置正好暴露重复元素；也可用「取负打标记」的变体
448. 找到所有数组中消失的数字 简单 归位后收集所有 arr[i] != i + 1 的下标，是本题结论的直接应用
645. 错误的集合 简单 一个值重复、一个值缺失，需要同时输出两者，归位后一次扫描即可定位
287. 寻找重复数 中等 明确禁止修改原数组，归位法失效，要转成链表环入口或值域二分
268. 丢失的数字 简单 只缺一个数，异或或求和公式就能 $O(1)$ 空间解决，不必真的排序
912. 排序数组 中等 值域任意的通用排序，只能退回 $O(n \log n)$，用来对照本题为什么能突破下界