LeetCode 补充题 165. 步长为 2 的循环交换排序判定
题目描述
给定长度为
n的整数数组nums，一次可以交换nums[i]与nums[(i+2)%n]，允许任意多次操作。判断能否变成非降序数组，判定过程不修改输入。空数组视为已排序。
示例 1：
输入：
nums = [3,1,2]
输出：true
解释： 先交换下标 0、2，再交换下标 0、1；后者可由i=1 的循环交换操作完成。
示例 2：
输入：
nums = [2,1,4,3]
输出：false
解释： 偶数长度下，偶数下标只能与偶数下标交换，无法把数值 1 放到下标 0。
示例 3：
输入：
nums = [3,2,1,4]
输出：true
解释： 交换下标 0、2 即得到[1,2,3,4]。
提示：
- 允许重复值，可以执行任意多次指定交换。
- 取模的下标指向同一数组。
- 空数组返回
true。 - 判定过程不修改输入。
题意分析
把数组下标作为顶点，允许交换的两个位置之间连边。元素不能离开所属连通分量，但可以沿路径逐步搬运，所以能否排序取决于每个分量拥有的值能否匹配目标位置。
解法：按交换连通分量比较多重集合
核心思路
[!blue]
步长为 2 的循环下标产生
gcd(n,2)个分量。n为奇数时所有位置连通，沿路径交换足以实现任意排列，因此总能排序；n为偶数时，奇偶下标分别构成两个独立分量。复制并排序得到唯一的非降序数值目标。对偶数下标，原数组值计数加 1，目标值计数减 1；差值全为 0 时该分量能完成所需重排。全部元素的多重集合本就相同，因此偶数分量匹配也保证奇数分量匹配。
必须比较次数而非仅比较集合，以覆盖重复值。输入保持只读；空数组的差值表为空，返回 true，长度为 2 时两个位置各自独立，只有已经有序才会通过。
解题步骤
- 非空奇数长度时所有下标连通，直接可排序。
- 偶数长度复制并排序数组，分别统计原数组和目标数组偶数下标的值频差。
- 频差全为 0 即可，奇数下标部分由全体多重集合相同自动保证；空数组自然为 true。
代码实现
class Solution {
public boolean canSort(int[] a) {
if (a.length % 2 == 1) {
return true;
}
int[] sorted = a.clone();
Arrays.sort(sorted);
Map<Integer, Integer> counts = new HashMap<>();
for (int i = 0; i < a.length; i += 2) {
counts.merge(a[i], 1, Integer::sum);
counts.merge(sorted[i], -1, Integer::sum);
}
for (int count : counts.values()) {
if (count != 0) {
return false;
}
}
return true;
}
}
import "sort"
func canSort(a []int) bool {
if len(a)%2 == 1 {
return true
}
sorted := append([]int(nil), a...)
sort.Ints(sorted)
counts := map[int]int{}
for i := 0; i < len(a); i += 2 {
counts[a[i]]++
counts[sorted[i]]--
}
for _, count := range counts {
if count != 0 {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：奇数长度为 $O(1)$；偶数长度为 $O(n \log n)$。
- 空间复杂度：奇数长度为 $O(1)$；偶数长度额外空间为 $O(n)$。
关键点总结
[!green]
连接路径上的交换足以在分量内部搬运元素；能否排序取决于每个分量中的值是否匹配目标，不要求每个值唯一。
易错点总结
[!yellow]
偶数长度只能在同奇偶下标间交换；存在重复值时必须比较出现次数，而非集合是否包含。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1202. 交换字符串中的元素 | 中等 | 都利用交换图的连通分量内部可任意重排；本题非空数组长度为奇数时全部下标连通，为偶数时才分成奇、偶下标两组。 |
| 补充题 154. 最大公约数 | 简单 | 非空模环中步长 2 的连通分量数量由 gcd(n,2) 决定，解释了长度的奇偶分支。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！