常见编程模式之循环排序
5. 循环排序（Cyclic Sort）
基本原理及应用场景
循环排序模式描述了一种解决包含给定范围数字的数组问题的有趣方法。具体来说，我们遍历数组的每一位数字，如果当前数字不在正确的索引上，则将其与正确的索引交换，如下图所示。如果直接把每个数字放到正确的索引上，会产生平方级的时间复杂度，而循环排序模式则可以提供线性的时间复杂度。
在以下场景中，我们可能会用到循环排序模式：
- 问题涉及给定范围的排序数组
- 问题需要找出排序数组中的缺失/重复/最小值
经典例题
268. 缺失数字（Easy）
给定一个包含
0, 1, 2, ..., n中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
「示例」：
输入: [3,0,1]
输出: 2
本题可以采用循环排序模式求解。我们遍历数组的每一位数字，判断其是否位于正确的索引上。遍历完成后再一次遍历数组，找出索引与值不相等的数字即为缺失数字。具体的代码实现如下：
class Solution:
def missingNumber(self, nums: List[int]) -> int:
start = 0
while start < len(nums):
num = nums[start]
if num < len(nums) and num != start: # 可以换成 nums[num] != num
# 可能执行多次交换，否则存在不完全排序
nums[start], nums[num] = nums[num], nums[start]
else:
start += 1
for i in range(len(nums)): # 遍历数组找出缺失数字
if nums[i] != i:
return i
return len(nums) # 可能缺失的为最后一位
这道题还有一些其他的解法，比较巧妙的是位运算和数学解法。位运算的思路为对一个数进行两次完全相同的异或运算会得到原来的数，因此将
与输入数组进行异或，最终的结果即为异或的数字。实际操作时可以通过一次循环完成所有的异或运算（将每一个数与其下标进行异或，初始值为
）：
class Solution:
def missingNumber(self, nums):
missing = len(nums)
for i, num in enumerate(nums):
missing ^= i ^ num
return missing
数学解法则是直接基于高斯求和公式求出
的和，减去数组中所有数的和，即为缺失数字：
class Solution:
def missingNumber(self, nums):
expected_sum = len(nums)*(len(nums)+1)//2
actual_sum = sum(nums)
return expected_sum - actual_sum
442. 数组中重复的数据（Medium）
给定一个整数数组 a，其中 1 ≤ a[i] ≤ n（n 为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。 你可以不用到任何额外空间并在 O(n) 时间复杂度内解决这个问题吗？
「示例」：
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
本题可以使用循环排序求解。利用数组的下标（注意要减 1）对其进行遍历排序，交换索引与值不相等的元素，最后遍历数组输出即可。具体代码实现如下：
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
start = 0
res = []
while start < len(nums): # 用for循环也可
num = nums[start]
# 注意判断条件的设置，当前位的数字对应的索引指向的数字不符合要求时交换
if nums[num - 1] != num: # 用start比可能陷入死循环，因为存在重复数字
nums[start], nums[num - 1] = nums[num - 1], nums[start]
else:
start += 1
for i in range(len(nums)):
if nums[i] != i + 1:
res.append(nums[i])
return res
还有一种比较巧妙的解法是考虑到元素最多出现两次，因此可以通过遍历数组对当前值对应的索引进行符号翻转，只有出现两次的元素会查询到负值。具体代码实现如下：
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
for i in range(len(nums)):
index = abs(nums[i]) -1 # 可能已经为负了
if nums[index] > 0: # 大于0说明当前值还未被翻转（即第一次查询）
nums[index] *= -1
else: # 否则是第二次查询，该元素必重复出现
res.append(index + 1)
return res
41. 缺失的第一个正数（Hard）
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
「示例」：
输入: [1,2,0]
输出: 3
这道题也可以使用循环排序求解，思路与上一题基本一致：假定数组包含
，将数组中的数移到其对应的索引的位置，恢复后再遍历数组即可找到第一个缺失的正数。代码实现如下：
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
这道题也可以利用索引对数组进行标记，具体思路如下图所示：
代码实现如下：
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
for i in range(n):
num = abs(nums[i])
if num <= n:
nums[num - 1] = -abs(nums[num - 1]) # 防止重复元素，保证为负
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1
其他类似的题目列表：
- LeetCode 448-「找到所有数组中消失的数字」（Easy）
- LeetCode 645-「错误的集合」（Easy）