Пост

Алгосы от Влада, часть 5. Циклическая сортировка

Опубликовано
Автор Крыловский Владислав
8 мин. чтения
Алгосы от Влада, часть 5. Циклическая сортировка

Введение

Паттерн циклической сортировки — это интересный подход для решения задач с массивами, содержащими числа в заданном диапазоне. Он особенно эффективен при работе с массивами, содержащими числа от 1 до ‘n’ или аналогичными ограниченными диапазонами.

Основная концепция

Постановка задачи

  • Нам дан массив, содержащий ‘n’ объектов
  • Каждому объекту был присвоен уникальный номер от 1 до ‘n’ в зависимости от порядка их создания
  • Задача — отсортировать объекты на месте по их порядковому номеру создания
  • Массив содержит числа из диапазона от 1 до ‘n’

Ключевая идея

Поскольку входной массив содержит числа в диапазоне от 1 до ‘n’, мы можем использовать этот факт для разработки эффективного метода сортировки. Мы можем попробовать разместить каждое число на его правильное место: поместить ‘1’ по индексу ‘0’, ‘2’ по индексу ‘1’ и так далее.

Подход алгоритма

  1. Проходим по массиву по одному числу за раз
  2. Если текущее число не на своём правильном индексе, меняем его местами с числом на его правильном индексе
  3. Продолжаем этот процесс, пока все числа не окажутся на правильных позициях
  4. Таким образом, мы проходим через все числа и размещаем их на правильных индексах, сортируя весь массив

Визуализация алгоритма

Рассмотрим пошаговую работу алгоритма на примере массива [2, 6, 4, 3, 1, 5]:

Шаг 1: Начинаем с индекса 0 (значение 2)

1
2
3

[2, 6, 4, 3, 1, 5]
 ↑
start

Число ‘2’ не на своём месте (должно быть по индексу 1). Меняем местами с числом по индексу 1:

Шаг 2: После обмена 2 ↔ 6

1
2
3

[6, 2, 4, 3, 1, 5]
 ↑
start

Теперь ‘2’ на правильном месте (индекс 1). Но ‘6’ всё ещё не на своём месте (должно быть по индексу 5). Меняем местами с числом по индексу 5:

Шаг 3: После обмена 6 ↔ 5

1
2
3

[5, 2, 4, 3, 1, 6]
 ↑
start

Теперь ‘6’ на правильном месте. Но ‘5’ не на своём месте (должно быть по индексу 4). Меняем местами с числом по индексу 4:

Шаг 4: После обмена 5 ↔ 1

1
2
3

[1, 2, 4, 3, 5, 6]
 ↑
start

Теперь ‘1’ на правильном месте (индекс 0). Переходим к следующему индексу.

Шаг 5: Индекс 1 (значение 2)

1
2
3

[1, 2, 4, 3, 5, 6]
    ↑
   start

‘2’ уже на правильном месте. Переходим дальше.

Шаг 6: Индекс 2 (значение 4)

1
2
3

[1, 2, 4, 3, 5, 6]
       ↑
      start

‘4’ не на своём месте (должно быть по индексу 3). Меняем местами с числом по индексу 3:

Шаг 7: После обмена 4 ↔ 3

1
2
3

[1, 2, 3, 4, 5, 6]
       ↑
      start

Теперь и ‘3’, и ‘4’ на своих местах. Проверяем оставшиеся элементы — все на своих местах!

Результат: [1, 2, 3, 4, 5, 6] — массив отсортирован!

Циклическая сортировка (простой уровень)

Условие задачи

Нам дан массив, содержащий числа от 1 до ‘n’. Массив может иметь дубликаты, что означает, что некоторые числа будут отсутствовать. Найдите все пропущенные числа.

Решение

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

package main

import "fmt"

func cyclicSort(nums []int) {
    i := 0
    for i < len(nums) {
        // Вычисляем правильный индекс для текущего числа
        j := nums[i] - 1
        
        // Если число не на правильной позиции
        if nums[i] != nums[j] {
            // Меняем местами с числом на правильной позиции
            nums[i], nums[j] = nums[j], nums[i]
        } else {
            // Переходим к следующей позиции
            i++
        }
    }
}

func main() {
    nums := []int{3, 1, 5, 4, 2}
    fmt.Println("Исходный массив:", nums)
    
    cyclicSort(nums)
    fmt.Println("Отсортированный массив:", nums)
    
    nums2 := []int{2, 6, 4, 3, 1, 5}
    fmt.Println("\nИсходный массив:", nums2)
    
    cyclicSort(nums2)
    fmt.Println("Отсортированный массив:", nums2)
    
    nums3 := []int{1, 5, 6, 4, 3, 2}
    fmt.Println("\nИсходный массив:", nums3)
    
    cyclicSort(nums3)
    fmt.Println("Отсортированный массив:", nums3)
}

Вывод:

1
2
3
4
5
6
7
8

Исходный массив: [3 1 5 4 2]
Отсортированный массив: [1 2 3 4 5]

Исходный массив: [2 6 4 3 1 5]
Отсортированный массив: [1 2 3 4 5 6]

Исходный массив: [1 5 6 4 3 2]
Отсортированный массив: [1 2 3 4 5 6]

Временная сложность

Временная сложность алгоритма составляет \(O(n)\). Хотя внешне алгоритм выглядит так, будто он работает за \(O(n^2)\) из-за вложенного цикла while, на самом деле каждое число перемещается максимум один раз на свою правильную позицию.

Пространственная сложность

Пространственная сложность алгоритма равна \(O(1)\), так как сортировка выполняется на месте без использования дополнительной памяти.

Найти пропущенное число (простой уровень)

Условие задачи

Нам дан массив, содержащий числа от 0 до ‘n’, кроме одного числа. Найдите пропущенное число.

Решение

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

package main

import "fmt"

func findMissingNumber(nums []int) int {
    i := 0
    n := len(nums)
    
    // Сортируем массив циклической сортировкой
    for i < n {
        j := nums[i]
        if nums[i] < n && nums[i] != nums[j] {
            nums[i], nums[j] = nums[j], nums[i]
        } else {
            i++
        }
    }
    
    // Находим первое число, не совпадающее со своим индексом
    for i := 0; i < n; i++ {
        if nums[i] != i {
            return i
        }
    }
    
    // Если все числа на своих местах, пропущено число n
    return n
}

// Альтернативное решение через XOR (более эффективное)
func findMissingNumberXOR(nums []int) int {
    n := len(nums)
    
    // XOR всех чисел от 0 до n
    xor1 := 0
    for i := 0; i <= n; i++ {
        xor1 ^= i
    }
    
    // XOR всех чисел в массиве
    xor2 := 0
    for i := 0; i < n; i++ {
        xor2 ^= nums[i]
    }
    
    // Результат XOR даст пропущенное число
    return xor1 ^ xor2
}

func main() {
    fmt.Println("Пропущенное число:", findMissingNumber([]int{4, 0, 3, 1}))
    fmt.Println("Пропущенное число:", findMissingNumber([]int{8, 3, 5, 2, 4, 6, 0, 1}))
    
    fmt.Println("\nИспользуя XOR:")
    fmt.Println("Пропущенное число:", findMissingNumberXOR([]int{4, 0, 3, 1}))
    fmt.Println("Пропущенное число:", findMissingNumberXOR([]int{8, 3, 5, 2, 4, 6, 0, 1}))
}

Вывод:

1
2
3
4
5
6

Пропущенное число: 2
Пропущенное число: 7

Используя XOR:
Пропущенное число: 2
Пропущенное число: 7

Найти все пропущенные числа (простой уровень)

Условие задачи

Нам дан несортированный массив, содержащий числа из диапазона от 1 до ‘n’. Массив может иметь дубликаты, что означает, что некоторые числа будут отсутствовать. Найдите все пропущенные числа.

Решение

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

package main

import "fmt"

func findAllMissingNumbers(nums []int) []int {
    i := 0
    for i < len(nums) {
        j := nums[i] - 1
        if nums[i] != nums[j] {
            nums[i], nums[j] = nums[j], nums[i]
        } else {
            i++
        }
    }
    
    missingNumbers := []int{}
    
    for i := 0; i < len(nums); i++ {
        if nums[i] != i+1 {
            missingNumbers = append(missingNumbers, i+1)
        }
    }
    
    return missingNumbers
}

func main() {
    fmt.Println("Пропущенные числа:", findAllMissingNumbers([]int{2, 3, 1, 8, 2, 3, 5, 1}))
    fmt.Println("Пропущенные числа:", findAllMissingNumbers([]int{2, 4, 1, 2}))
    fmt.Println("Пропущенные числа:", findAllMissingNumbers([]int{2, 3, 2, 1}))
}

Вывод:

1
2
3

Пропущенные числа: [4 6 7]
Пропущенные числа: [3]
Пропущенные числа: [4]

Когда использовать паттерн Cyclic Sort?

Этот паттерн идеально подходит для:

  • Массивов с числами в определённом диапазоне (от 1 до n)
  • Поиска пропущенных чисел в таких массивах
  • Обнаружения дублированных чисел
  • Сортировки на месте с минимальной пространственной сложностью
  • Задач, где нужно определить, какие числа отсутствуют в последовательности

Преимущества эффективности

Временная сложность: \(O(n)\) — каждое число перемещается максимум один раз на свою правильную позицию

Пространственная сложность: \(O(1)\) — сортировка выполняется на месте без дополнительной памяти

Ключевое преимущество: Вместо использования традиционных алгоритмов сортировки с временной сложностью \(O(n \log n)\), циклическая сортировка использует ограничение на диапазон чисел для достижения временной сложности \(O(n)\).

Подход к решению задач

Паттерн работает следующим образом:

  1. Использование ограничения, что числа находятся в диапазоне от 1 до ‘n’
  2. Сопоставление чисел с индексами (число ‘x’ должно быть по индексу ‘x-1’)
  3. Обмен элементов местами, пока каждый не окажется на правильной позиции
  4. Выявление аномалий (пропущенные числа, дубликаты) после сортировки

Похожие задания

5. Pattern: Cyclic Sort

  1. Cyclic Sort (easy) Leetcode
  2. Find the Missing Number (easy) Leetcode
  3. Find all Missing Numbers (easy) Leetcode
  4. Find the Duplicate Number (easy) Leetcode
  5. Find all Duplicate Numbers (easy) Leetcode
  6. Find the Corrupt Pair (easy) Leetcode
  7. Find the Smallest Missing Positive Number (medium) Leetcode
  8. Find the First K Missing Positive Numbers (hard) Leetcode
Programming, Interview
algovlad golang leetcode coding
Авторский пост защищен лицензией CC BY 4.0 .

Популярные теги

golang algovlad coding leetcode build cheatsheet ci/cd tests