Cyclic Sort 在“集合错位”问题中的无限循环陷阱与修复方案-Python教程-PHP中文网

Cyclic Sort 在“集合错位”问题中的无限循环陷阱与修复方案

本文详解 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 <blockquote>
<p>? <strong>关键改进点</strong>：</p>
<ul>
<li>
<code>correct_idx = nums[i] - 1</code> 在交换前一次性计算，确保索引稳定；</li>
<li>增加 <code>and i != correct_idx</code> 条件，避免将 <code>nums[i]</code> 与自身比较（如 <code>nums = [1]</code> 时 <code>i == correct_idx == 0</code>）；</li>
<li>逻辑更清晰：先判重复，再判就位，最后才交换。</li>
</ul>
</blockquote><h3>? 验证示例</h3><p>对 <code>nums = [2, 3, 2]</code>：</p>

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。