Cyclic Sort

Posted on

常用但鲜为人知的循环排序。核心理念是：将元素交换到正确的位置，继而获取某个 range 内缺失的数字。其中，缺失数字为索引值，已有数字为元素值。警惕 desired index 可能造成的数组越界。

This pattern describes an interesting approach to deal with problems involving arrays containing numbers in a given range. For example, take the following problem:

You are given an unsorted array containing numbers taken from the range “1” to “n”. The array can have duplicates, which means that some numbers will be missing. Find all the missing numbers.

To efficiently solve this problem, we can use the fact that the input array contains numbers in the range of “1” to “n”. For example, to efficiently sort the array, we can try placing each number in its correct place, i.e., placing “1” at index “0”, placing “2” at index “1”, and so on. Once we are done with the sorting, we can iterate the array to find all indices that are missing the correct numbers. These will be our required numbers.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = len(nums)

i = 0
while i < n:
    j = nums[i] - 1
    if 0 <= j < n and nums[i] != nums[j]:  # avoid index out of bounds
        nums[i], nums[j] = nums[j], nums[i]
        continue

    i += 1

for i in range(n):
    if nums[i] != i + 1:
        return i + 1

return n + 1

LeetCode

765. Couples Holding Hands
268. Missing Number
448. Find All Numbers Disappeared in an Array
287. Find the Duplicate Number
442. Find All Duplicates in an Array
645. Set Mismatch
41. First Missing Positive
1539. Kth Missing Positive Number