循环排序(Cyclic Sort)
基本原理及应用场景
循环排序模式描述了一种解决包含给定范围数字的数组问题的有趣方法。...如果直接把每个数字放到正确的索引上,会产生平方级的时间复杂度,而循环排序模式则可以提供线性的时间复杂度。
?...在以下场景中,我们可能会用到循环排序模式:
问题涉及给定范围的排序数组
问题需要找出排序数组中的缺失/重复/最小值
经典例题
268....「示例」:
输入: [3,0,1]
输出: 2
本题可以采用循环排序模式求解。我们遍历数组的每一位数字,判断其是否位于正确的索引上。遍历完成后再一次遍历数组,找出索引与值不相等的数字即为缺失数字。...「示例」:
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
本题可以使用循环排序求解。