Найти пропущенное число

Найти пропущенное число

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

Дан массив, содержащий n различных чисел из диапазона от 0 до n. Одно число в нём отсутствует. Найдите пропущенное число.

Пример 1:

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

Пример 2:

  • Вход: [8, 3, 5, 2, 4, 6, 0, 1]
  • Выход: 7

Решение

Размещаем каждое число x, которое меньше длины массива, по индексу x. Значение n пропускаем, потому что в массиве нет индекса n.

После циклической сортировки первый индекс i, для которого nums[i] != i, и будет пропущенным числом. Если все числа находятся на своих индексах, пропущено число 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

package main

import "fmt"

func findMissingNumber(nums []int) int {
	i := 0
	n := len(nums)

	for i < n {
		correctIndex := nums[i]
		if nums[i] < n && nums[i] != nums[correctIndex] {
			nums[i], nums[correctIndex] = nums[correctIndex], nums[i]
		} else {
			i++
		}
	}

	for i, number := range nums {
		if number != i {
			return i
		}
	}

	return n
}

func findMissingNumberXOR(nums []int) int {
	n := len(nums)

	xor1 := 0
	for i := 0; i <= n; i++ {
		xor1 ^= i
	}

	xor2 := 0
	for _, number := range nums {
		xor2 ^= number
	}

	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

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

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

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

Оба варианта используют \(O(1)\) дополнительной памяти. Решение с циклической сортировкой изменяет входной массив.