循环排序（Cyclic Sort）的进阶应用：寻找重复和缺失的数

题目描述
给定一个长度为 n 的数组 nums，包含从 1 到 n 的整数，但由于某些原因，其中一个数重复出现，导致另一个数缺失。要求在不使用额外空间且时间复杂度为 O(n) 的条件下，找到重复的数和缺失的数。

例如：
输入：nums = [3, 1, 3, 4, 2]（n=5）
输出：重复数=3，缺失数=5

解题过程

步骤 1：理解问题核心

• 数组本应包含 1 到 n 各一次，但实际有且仅有一个数重复（假设重复一次），导致另一个数缺失。
• 关键观察：若将每个数放到其正确位置（即 nums[i] 应放在索引 nums[i]-1 处），通过交换操作可部分排序数组，从而发现问题。

步骤 2：循环排序的基本思路

1. 遍历数组，对于每个索引 i：
   • 若 nums[i] 不在其正确位置（即 nums[i] ≠ nums[nums[i]-1]），则将其与正确位置的数交换。
   • 若 nums[i] 已在正确位置，或正确位置已存在相同的数（表示重复），则 i++。
2. 排序完成后，正常情况下应有 nums[i] = i+1。若某个位置 j 的值不为 j+1，则 j+1 是缺失的数；而重复的数可通过交换过程中的冲突发现。

步骤 3：具体操作演示（以 nums = [3, 1, 3, 4, 2] 为例）

• i=0：nums[0]=3，正确位置应为索引 2（即值 3 应放在 nums[2]）。交换 nums[0] 与 nums[2]：
  [3, 1, 3, 4, 2] → [3, 1, 3, 4, 2]（交换后 nums[0]=3 仍不匹配？注意：交换后应重新检查 i=0！）
  实际上，交换后数组变为 [3, 1, 3, 4, 2]（因 nums[0]=3 与 nums[2]=3 相同，此时发现重复）。

  更严谨的流程：

  • i=0：nums[0]=3，应去索引 2。但 nums[2]=3，已等于当前值，说明 3 重复。记录重复数=3，i++。
  • i=1：nums[1]=1，正确位置索引 0（值 1 应放 nums[0]）。交换 nums[1] 与 nums[0]：
    [3, 1, 3, 4, 2] → [1, 3, 3, 4, 2]。
  • i=1：交换后 nums[1]=3，应去索引 2。但 nums[2]=3，重复已记录，i++。
  • i=2：nums[2]=3，正确位置索引 2，无需操作。
  • 继续遍历至结束，数组为 [1, 3, 3, 4, 2]。

步骤 4：定位缺失的数
遍历排序后数组，若 nums[i] ≠ i+1，则 i+1 是缺失的数。本例中：

• i=2：nums[2]=3 ≠ 3？不对，应比较 nums[2] 和 3？实际上：

  • 索引 0: nums[0]=1 ✓
  • 索引 1: nums[1]=3 ≠ 2 → 缺失数=2？但 2 在索引 4 存在，说明需修正。

  问题：因重复数占位，直接比较会出错。正确方法：
  在交换过程中，若发现目标位置已存在相同值，则记录重复数；最终缺失数 = (1+2+...+n) - (当前数组去重后总和)，但去重需额外空间。

  改进：缺失数 = 重复数 - (当前数组总和 - 理想总和(1+...+n))
  理想总和 S = n(n+1)/2 = 15
  当前总和 = 3+1+3+4+2 = 13
  差值 = 13 - 15 = -2 → 缺失数 = 重复数 - (-2) = 3 + 2 = 5。

步骤 5：算法总结

1. 使用循环排序，交换时若 nums[i] 与 nums[nums[i]-1] 相等且 i ≠ nums[i]-1，则记录重复数。
2. 计算缺失数：缺失数 = 重复数 - (sum(nums) - n(n+1)/2)。

代码框架（Python）

def findErrorNums(nums):
    n = len(nums)
    duplicate = -1
    for i in range(n):
        while nums[i] != i + 1:
            correct_index = nums[i] - 1
            if nums[i] == nums[correct_index]:
                duplicate = nums[i]
                break
            else:
                nums[i], nums[correct_index] = nums[correct_index], nums[i]
    total_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    missing = duplicate - (actual_sum - total_sum)
    return [duplicate, missing]