В этом посте рассматривается второе решение для урока 3 с уменьшением временной сложности. Чтобы получить доступ к проблеме, нажмите следующую ссылку.
Описание задания
Дан массив A, состоящий из N различных целых чисел. Массив содержит целые числа в диапазоне [1..(N + 1)], что означает отсутствие ровно одного элемента.
Ваша цель — найти этот недостающий элемент.
Напишите функцию:
защитное решение (A)
это, учитывая массив A, возвращает значение отсутствующего элемента.
Например, дан массив A такой, что:
A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
функция должна вернуть 4, так как это отсутствующий элемент.
Напишите эффективный алгоритм для следующих предположений:
- N — целое число в диапазоне [0..100 000];
- все элементы A различны;
- каждый элемент массива A является целым числом в диапазоне [1..(N + 1)].
Авторские права, 2009–2020 гг., принадлежат Codility Limited. Все права защищены. Несанкционированное копирование, публикация или разглашение запрещено.
Ключевой момент
- Массив должен начинаться с 1. Если нет, ответ равен 1.
- Для более быстрого расчета линейный поиск элементов после сортировки неэффективен.
- Вы можете использовать уравнение «сумма последовательности».
Решение (с использованием Python)
def solution(A):
if(len(A) == 0): return 1
elif(len(A) == 1):
if(A[0] == 1): return 2
else: return 1
else:
n, sum_val = len(A) + 1, sum(A)
return int(((n*(n+1)) / 2) - sum_val)
Используйте приведенное выше решение для справки.
Я рекомендую вам написать собственный исходный код.
