循环排序（Cyclic Sort）的进阶应用：寻找数组中重复和缺失的数（多元素版本） 题目描述 给定一个长度为 n 的数组 nums ，其中包含从 1 到 n 的整数，但由于某些错误，数组中的某些数字重复出现，而另一些数字缺失。要求在不使用额外空间且时间复杂度为 O(n) 的条件下，找出所有重复的数字和缺失的数字。例如，对于输入 [4,3,2,7,8,2,3,1] ，输出应为重复数字 [2,3] 和缺失数字 [5,6] 。 解题过程 步骤 1：理解问题核心 数组本应包含 1 到 n 的不重复整数，但实际存在重复和缺失。 关键观察：若数组有序，则每个数字 x 应出现在索引 x-1 的位置（因为索引从 0 开始）。 目标：通过原地重排数组，利用索引与值的映射关系找出异常值。 步骤 2：循环排序的基本思想 循环排序的核心是通过交换将每个数字放到其正确位置（即 nums[i] 应等于 i+1 ）。具体流程： 遍历数组，对于每个索引 i ： 若 nums[i] 不在其正确位置（即 nums[i] ≠ i+1 ），且正确位置（索引 nums[i]-1 ）上的数字与 nums[i] 不同，则交换 nums[i] 和 nums[nums[i]-1] 。 若正确位置上的数字已等于 nums[i] ，说明 nums[i] 是重复数字，跳过当前 i 。 重复直到数组无法继续交换。 步骤 3：应用循环排序到示例 以 nums = [4,3,2,7,8,2,3,1] （n=8）为例： i=0 ： nums[0]=4 ，正确位置为索引 3（值 7），交换后为 [7,3,2,4,8,2,3,1] 。 i=0 ： nums[0]=7 ，正确位置为索引 6（值 3），交换后为 [3,3,2,4,8,2,7,1] 。 i=0 ： nums[0]=3 ，正确位置为索引 2（值 2），交换后为 [2,3,3,4,8,2,7,1] 。 i=0 ： nums[0]=2 ，正确位置为索引 1（值 3），交换后为 [3,2,3,4,8,2,7,1] 。 i=0 ： nums[0]=3 ，正确位置为索引 2（值 3），但该位置已正确，发现重复（3 在索引 0 和 2 均出现），跳过 i=0。 继续处理 i=1 到 i=7，最终数组变为 [1,2,3,4,3,2,7,8] 。 步骤 4：识别重复和缺失的数字 排序后，遍历数组： 若 nums[i] ≠ i+1 ，则说明： 索引 i 处的数字 nums[i] 是重复数字（因为它占用了缺失数字的位置）。 数字 i+1 是缺失数字。 示例中： i=4： nums[4]=3 ≠ 5 → 重复数字 3，缺失数字 5。 i=5： nums[5]=2 ≠ 6 → 重复数字 2，缺失数字 6。 i=6 和 i=7 正确，忽略。 输出：重复数字 [2,3] ，缺失数字 [5,6] 。 步骤 5：处理重复数字的去重 由于重复数字可能多次出现在错误位置，需用集合存储结果以避免重复记录。 总结 通过循环排序将数字归位，再扫描异常位置，即可高效找出重复和缺失的数字。该方法满足 O(n) 时间和 O(1) 空间的要求，适用于数据范围已知且连续的场景。