---

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

Дан несортированный массив из n+1 чисел в диапазоне от 1 до n. В массиве есть только одно повторяющееся число, но оно может встречаться несколько раз. Найдите это число без дополнительной памяти. Входной массив разрешено изменять.

Пример 1:

• Вход: [1, 4, 4, 3, 2]
• Выход: 4

Пример 2:

• Вход: [2, 1, 3, 3, 5, 4]
• Выход: 3

Пример 3:

• Вход: [2, 4, 1, 4, 4]
• Выход: 4

Решение

Задача следует паттерну циклической сортировки и похожа на поиск пропущенного числа. Будем пытаться поставить каждое число на правильный индекс: число x должно находиться по индексу x-1.

Если текущее число стоит не на своём месте, сравниваем его с числом на целевом индексе. Когда значения совпадают, дальнейший обмен невозможен: мы нашли повторяющееся число. В противном случае меняем числа местами и продолжаем сортировку.

Код

package main

import "fmt"

func findDuplicate(nums []int) int {
	i := 0
	for i < len(nums) {
		if nums[i] == i+1 {
			i++
			continue
		}

		correctIndex := nums[i] - 1
		if nums[i] == nums[correctIndex] {
			return nums[i]
		}

		nums[i], nums[correctIndex] = nums[correctIndex], nums[i]
	}

	return -1
}

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

Вывод:

4
3
4

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

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

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

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

---