排序算法之：循环排序（Cyclic Sort）的进阶应用——寻找重复和缺失的数（多元素版本）

题目描述：给定一个长度为 n 的数组，其中包含从 1 到 n 的整数，但有些数字出现了多次，有些数字缺失。数组可能包含多个重复和缺失的数字。请设计一个算法，找出所有重复的数字和所有缺失的数字。要求时间复杂度为 O(n)，空间复杂度为 O(1)（除了存储结果的数组）。

解题过程：

1. 问题分析

   • 数组包含 n 个元素，数值范围应该是 1 到 n
   • 由于存在重复和缺失，某些数字会出现多次，某些数字不会出现
   • 我们需要找出所有重复出现的数字和所有缺失的数字

2. 循环排序的基本思想

   • 循环排序的核心思想是将每个数字放到它应该在的位置上（即 nums[i] 应该等于 i+1）
   • 对于每个位置 i，如果 nums[i] ≠ i+1，就将 nums[i] 放到它应该在的位置 nums[i]-1
   • 重复这个过程直到当前数字被放到正确位置，或者发现重复

3. 多元素版本的循环排序实现

   def cyclic_sort(nums):
       i = 0
       n = len(nums)
       while i < n:
           # 如果当前数字不在正确位置，且目标位置的数字不是正确的
           if nums[i] != i + 1 and nums[nums[i] - 1] != nums[i]:
               # 交换当前数字到正确位置
               correct_pos = nums[i] - 1
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               i += 1
   

4. 寻找重复和缺失的数字

   • 排序完成后，遍历数组
   • 如果 nums[i] ≠ i+1，说明位置 i+1 上出现了错误的数字
   • 当前数字 nums[i] 是重复的数字（因为它出现在了错误的位置）
   • 位置 i+1 上应该出现的数字是缺失的数字

5. 完整算法实现

   def find_all_duplicates_and_missing(nums):
       n = len(nums)
       i = 0
   
       # 第一步：使用循环排序将数字放到正确位置
       while i < n:
           correct_pos = nums[i] - 1
           if nums[i] != nums[correct_pos]:
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               i += 1
   
       # 第二步：找出重复和缺失的数字
       duplicates = []
       missing = []
   
       for i in range(n):
           if nums[i] != i + 1:
               duplicates.append(nums[i])  # 当前位置的数字是重复的
               missing.append(i + 1)       # 应该在这个位置的数字缺失了
   
       return duplicates, missing
   

6. 算法正确性证明

   • 循环排序确保每个数字最终要么在正确位置，要么因为重复而无法移动
   • 遍历时，每个位置 i 检查 nums[i] 是否等于 i+1
   • 如果不相等，说明：
     • nums[i] 是重复数字（因为它占据了其他数字的位置）
     • i+1 是缺失数字（因为正确数字没有出现在这个位置）

7. 复杂度分析

   • 时间复杂度：O(n)，每个元素最多被交换一次到正确位置
   • 空间复杂度：O(1)，除了存储结果的数组外，只使用了常数级别的额外空间

8. 边界情况处理

   • 空数组：直接返回空列表
   • 所有数字都正确：返回两个空列表
   • 多个重复和缺失的情况：算法能正确处理

这个算法巧妙地利用循环排序的特性，在 O(n) 时间复杂度和 O(1) 空间复杂度下解决了多重复多缺失的复杂问题。