本文详解 leetcode “set mismatch” 问题中使用 cyclic sort 时因 python 多重赋值求值顺序导致的无限循环问题，并提供安全、可复用的修复方案。
本文详解 leetcode “set mismatch” 问题中使用 cyclic sort 时因 python 多重赋值求值顺序导致的无限循环问题，并提供安全、可复用的修复方案。
在使用 Cyclic Sort 解决 LeetCode 645. Set Mismatch 问题时，目标是将数组 nums 中每个数字 x 放置到索引 x−1 处（即满足 nums[i] == i + 1），从而通过一次遍历快速定位重复值和缺失值。然而，一个看似简洁的交换写法：
nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
会引发严重逻辑错误——不是语法错误，而是语义陷阱。
? 根本原因：Python 多重赋值的求值顺序
Python 在执行 a, b = c, d 时，先完整计算右侧表达式（c 和 d），再按从左到右顺序执行左侧赋值。但关键在于：当左侧出现索引依赖（如 nums[nums[i] - 1]）时，nums[i] 在右侧已求值完毕；但左侧第二个位置 nums[nums[i] - 1] 中的 nums[i] 是赋值后的新值！
以输入 [2, 3, 2]（索引 0 处为 2）为例，首次进入循环时：
- 初始：
i = 0,nums = [2, 3, 2] - 右侧计算：
nums[nums[0]-1] → nums[2-1] → nums[1] → 3，nums[0] → 2→ 右侧元组为(3, 2) - 开始赋值：
- 先执行
nums[0] = 3→nums变为[3, 3, 2] -
再计算左侧第二项索引：
nums[0] - 1 → 3 - 1 = 2→ 即nums[2] - 执行
nums[2] = 2→nums变为[3, 3, 2]
- 先执行
注意：此时 nums[0] 已被改为 3，但原始意图是把原 nums[0]（即 2）交换到 nums[1]（因为 2−1=1）。由于索引动态变化，交换目标错位，导致 2 和 3 在索引 0 和 1 间反复“打滑”，陷入死循环。
✅ 正确解法：显式缓存目标索引
只需将目标索引 j = nums[i] - 1 提前计算并固定，再执行交换：
def findErrorNums(nums: List[int]) -> List[int]:
n = len(nums)
duplicated = 0
i = 0
while i < n:
correct_idx = nums[i] - 1 # ✅ 显式计算目标位置，避免后续变化
if nums[i] == nums[correct_idx] and i != correct_idx:
# 发现重复：当前数已在正确位置上（但索引不同），说明该数重复
duplicated = nums[i]
i += 1
elif nums[i] == i + 1:
# 已在正确位置
i += 1
else:
# 安全交换：索引已固定，无副作用
nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
# 扫描找缺失：首个不满足 nums[i] == i+1 的位置，缺失数为 i+1
for i in range(n):
if nums[i] != i + 1:
return [duplicated, i + 1]
return [duplicated, n] # 理论上不会到达此处? 关键改进点：
correct_idx = nums[i] - 1在交换前一次性计算，确保索引稳定；- 增加
and i != correct_idx条件，避免将nums[i]与自身比较（如nums = [1]时i == correct_idx == 0）；- 逻辑更清晰：先判重复，再判就位，最后才交换。
? 验证示例
对 nums = [2, 3, 2]：
-
i=0:correct_idx = 2-1 = 1→ 交换nums[0]与nums[1]→[3,2,2] -
i=0:correct_idx = 3-1 = 2→ 交换nums[0]与nums[2]→[2,2,3] -
i=0:nums[0]==2,correct_idx=1,nums[1]==2→ 发现重复2，记录并i++ -
i=1:nums[1]==2，correct_idx=1→i==correct_idx，跳过（不触发重复判定） -
i=2:nums[2]==3→ 就位，i++ - 扫描：
i=0→2✓,i=1→nums[1]=2✓,i=2→nums[2]=3✓→ 但n=3，应有1,2,3；实际nums=[2,2,3]→i=0时nums[0]=2≠1→ 缺失1？等等——需注意：此算法要求最终数组形态反映真实映射。
更鲁棒的扫描方式（推荐）：
# 替换原扫描部分：
for i in range(n):
if nums[i] != i + 1:
return [duplicated, i + 1]对 [2,2,3]：i=0 → nums[0]=2 ≠ 1 → 返回 [2,1]？❌ 错误。
问题在于：重复发生后，正确位置可能已被覆盖。标准做法是：Cyclic Sort 后，缺失数是第一个 nums[i] != i+1 的 i+1；而重复数是在交换过程中检测到的 nums[i]（当 nums[i] == nums[nums[i]-1] 且 i != nums[i]-1）。
因此，上述代码中重复判定逻辑需严格为：
if nums[i] == nums[correct_idx] and i != correct_idx:
duplicated = nums[i]
i += 1运行 [2,3,2] 全流程：
-
[2,3,2]→i=0,correct_idx=1,nums[0]==2,nums[1]==3→ 交换 →[3,2,2] -
[3,2,2]→i=0,correct_idx=2,nums[0]==3,nums[2]==2→ 交换 →[2,2,3] -
[2,2,3]→i=0,correct_idx=1,nums[0]==2,nums[1]==2→i(0) != correct_idx(1)→ ✅ 捕获duplicated = 2 - 继续
i=1:nums[1]==2,correct_idx=1→i==correct_idx→ 跳过（不重复判定） -
i=2:nums[2]==3→ 就位 - 扫描：
i=0→nums[0]=2≠1→ 缺失1？但期望输出是[2,1]？回顾题设：[2,3,2]表示 n=3，原集合应为{1,2,3}，现含两个2，缺1→ ✅ 正确！LeetCode 示例[1,2,2,4]输出[2,3]因 n=4，缺3。
故 [2,3,2] 正确答案是 [2,1]，而非 [2,3]（后者对应 n=4）。题干明确：“originally contains all numbers from 1 to n”，len(nums)=n，所以 [2,3,2] 的 n=3，缺失 1。
⚠️ 注意事项总结
-
永远不要在多重赋值左侧使用动态索引表达式（如
nums[nums[i]-1]），这是 Python 特有的坑； - Cyclic Sort 的核心是「每个数归位」，但需确保交换操作幂等且可终止；
- 边界检查不可省略：
i != correct_idx防止自比较； - 时间复杂度仍为 O(n)：每个元素最多被交换两次（进入正确位置或被换出）；
- 空间复杂度 O(1)，符合题目进阶要求。
掌握这一细节，你就能写出健壮、高效的 Cyclic Sort 实现，从容应对各类排列类算法题。
