Постановка задачи
Вам дан массив положительных чисел от 1 до n, так что присутствуют все числа от 1 до n, кроме одного числа «x». Вы должны найти «х». Входной массив не отсортирован.
Например, давайте посмотрим на приведенный ниже массив.
Подсказка
- Как бы вы вычислили сумму чисел от 1 до n?
Попробуйте сами
- C ++
- C ++
- C ++
- Java
- Java
- путь> Python
- JavaScript
- JavaScript
- Ruby
- Ruby
Python
int find_missing (const vector & input) {//TODO: Write - Your - Code return -1;}
Решение
- C ++
- путь> путь > C ++
- C ++
- путь> Java
- Java
- Python
- Python
- JavaScript
- JavaScript
- Рубин
- Рубин
int find_missing (const vector & input) {//вычисляем сумму всех элементов//во входном векторе auto sum_of_elements = std :: accumulate (input.begin (), input.end (), 0); //Отсутствует ровно 1 число int n = input. размер () + 1; int фактическая_сумма = (п * (п + 1))/2; return actual_sum - sum_of_elements;} недействительный тест (int n) {int missing_element = rand ()% n + 1; вектор v; for (int i = 1; i
Объяснение решения
Сложность времени выполнения
Линейная, O (n).
Сложность памяти
Константа, O ( 1).
Анализ решения
Наивное решение — просто искать каждое целое число от 1 до n во входном массиве, останавливая поиск как только появится недостающий номер. Поскольку входной массив не отсортирован, его временная сложность будет O ( n 2n^{2} n 2) .
Можете ли вы сделать лучше, чем O ( n 2 n ^ {2} n 2 )? Да.
Вы можете отсортировать массив, а затем выполнить линейное сканирование O (n), где вы сравните все последовательные элементы, чтобы найти недостающее число. Однако временная сложность этого алгоритма составляет O (n log n) из-за времени, затрачиваемого на сортировку.
Вы можете добиться большего. Вот линейное решение O (n), которое использует формулу суммы арифметических рядов.
Sum (1 — n) = n ( n + 1)2 frac {n (n + 1)} {2} 2 n (n + 1)
Вот шаги, чтобы найти недостающее число.
- Найдите сумму «sum_of_elements» всех чисел в массиве. Для этого потребуется линейное сканирование, O (n).
- Затем найдите сумму «ожидаемая_сумма» первых «n» чисел, используя формулу суммы арифметического ряда, т.е. (n * (n + 1)) /2.
- Разница между этими, например, «ожидаемая_ сумма — сумма_элементов», заключается в отсутствующем числе в массиве.
