LeetCode 补充题 15. 自然数数组的排序
题目描述
给定长度为
n的数组arr，它恰好包含1到n的所有整数，且每个整数只出现一次。请将数组原地排列为升序并返回。要求时间复杂度为 O(n)，额外空间复杂度为 O(1)。
示例 1：
输入：arr = [3,1,2,5,4]
输出：[1,2,3,4,5]
提示：
-
n = arr.length。 - 数组是
1到n的一个排列，不包含重复值或范围外的值。 - 不能直接给每个位置赋值
arr[i] = i + 1来构造答案，需要重新排列原有元素。 - 需要直接修改原数组，不能依赖额外的长度为 n 的数组。
题意分析
输入数组恰好是
1到n的一个排列，每个值出现一次，要求用线性时间、常数额外空间把它按升序排列。这里利用的是取值与位置的一一对应，不是对任意整数数组进行通用比较排序。排序完成后，值
v必须位于下标v - 1。因此读到一个错位值时，可以直接知道它的最终位置，通过交换将它送回去，而无需继续比较大小。
解法：值归位的原地交换
核心思路
[!blue]
从左到右检查下标
i。若arr[i] == i + 1，这个位置已经正确，直接继续；否则当前值应位于arr[i] - 1，先保存这个目标下标，再交换当前位置与目标位置。交换后，被送出的值已经到达正确位置，但换入
i的值可能仍然错位，因此需要在同一个下标持续交换，直到当前位置也正确。只交换一次不能保证完成这一位置的处理。每次有效交换都会新增至少一个正确位置。因为值互不相同，另一个位置不会再拿着相同的值来交换这个已归位位置；它以后被外层检查时，也会直接跳过。所以已经归位的值不会再次被移走。
正确位置的数量只增加，最多增加到
n，因此所有内层交换的总次数为线性，不是每个位置都要重新做一遍线性搜索。外层结束时每个下标都对应应有的值，数组自然已经有序。目标下标要在改写当前值之前保存。Java 先备份目标位置的旧值再完成交换，Go 的多重赋值会先求右侧值，两种方式都不会丢失换入数据。
解题步骤
- 长度不足二时直接返回；否则依次检查每个下标。
- 当前值未归位时，保存它的目标下标
arr[i] - 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;
}
}
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。
- 空间复杂度：$O(1)$，只使用下标和交换临时变量。
关键点总结
[!green]
- 值与下标一一对应，直接确定交换目标。
- 用 while 持续处理换入的值，而不是只交换一次。
- 目标下标先保存，避免改写 arr[i] 后再计算到错误位置。
- 有序输入无需交换，但仍会完成一遍线性扫描。
易错点总结
[!yellow]
- 目标下标不减一：值从一开始、下标从零开始，最大值应放在最后一个下标。
- 只用一次判断交换：换入的值还可能错位，需要持续处理当前下标。
- 覆盖当前值后再计算目标：会把新值当成原值，写入错误位置，应先固定目标下标。
- 用于存在重复值的数组：可能反复交换相同值而无法推进，本方法依赖输入恰好是一个排列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 41. 缺失的第一个正数 | 困难 | 都可把合法值交换到对应下标，本题每值唯一且都在1到n，缺失正数题还需防越界和重复循环。 |
| 补充题 101. 数组排序的最少交换次数 | 困难 | 位置映射形成置换环，本题直接归位排序，原题进一步统计最少交换次数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！