---

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

Дан несортированный массив из n чисел в диапазоне от 1 до n. Изначально массив содержал все числа от 1 до n, но из-за ошибки одно число продублировалось, а другое пропало. Найдите оба числа.

Первым элементом результата должно быть повторяющееся число, вторым — пропущенное.

Пример 1:

• Вход: [3, 1, 2, 5, 2]
• Выход: [2, 4]
• Объяснение: число 2 повторяется, а число 4 пропущено.

Пример 2:

• Вход: [3, 1, 2, 3, 6, 4]
• Выход: [3, 5]
• Объяснение: число 3 повторяется, а число 5 пропущено.

Решение

Задача следует паттерну циклической сортировки и похожа на поиск всех повторяющихся чисел. Сначала размещаем каждое число x по индексу x-1. После сортировки ищем единственную позицию, на которой находится неправильное число.

Значение на этой позиции — повторяющееся число, а номер позиции i+1 — пропущенное.

Код

package main

import "fmt"

func findCorruptPair(nums []int) []int {
	i := 0
	for i < len(nums) {
		correctIndex := nums[i] - 1
		if nums[i] != nums[correctIndex] {
			nums[i], nums[correctIndex] = nums[correctIndex], nums[i]
		} else {
			i++
		}
	}

	for i, number := range nums {
		if number != i+1 {
			return []int{number, i + 1}
		}
	}

	return nil
}

func main() {
	fmt.Println(findCorruptPair([]int{3, 1, 2, 5, 2}))
	fmt.Println(findCorruptPair([]int{3, 1, 2, 3, 6, 4}))
}

Вывод:

[2 4]
[3 5]

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

Временная сложность алгоритма равна \(O(n)\).

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

Алгоритм использует \(O(1)\) дополнительной памяти.

---