[Codility] Урок-04.3: MissingInteger

Поиск пропущенного значения в данном массиве обрабатывается в этом посте. Определение проблемы можно подтвердить по следующему URL-адресу.

Описание задания

Это демонстрационная задача.

Напишите функцию:

защитное решение (A)

что для заданного массива A из N целых чисел возвращается наименьшее положительное целое число (больше 0), которое не встречается в A.

Например, если A = [1, 3, 6, 4, 1, 2], функция должна вернуть 5.

Учитывая A = [1, 2, 3], функция должна вернуть 4.

Учитывая A = [−1, −3], функция должна возвращать 1.

Напишите эффективный алгоритм для следующих предположений:

• N — целое число в диапазоне [1..100 000];
• каждый элемент массива A является целым числом в диапазоне [−1 000 000..1 000 000].

Авторские права, 2009–2020 гг., принадлежат Codility Limited. Все права защищены. Несанкционированное копирование, публикация или разглашение запрещено.

Ключевой момент

• Применение алгоритма сортировки перед поиском пропущенного значения может повысить эффективность.
• Некоторые хитрые условные операции для прямого возврата ответа до проведения линейного поиска позволяют избежать ненужной работы. Это значит, что дает эффективность.

Решение (с использованием Python)

def solution(A):
    A.sort()
    if(A[-1] <= 0): return 1 # Trick-1
    try: _ = A.index(1) # Trick-2
    except: return 1
    int_min = A[-1] + 1
    for idx in range(len(A)-1):
        if(A[idx] <= 0 or A[idx+1] <= 0): continue
        if(abs(A[idx] - A[idx+1]) > 1):
            int_min = min(int_min, A[idx] + 1)
            break
    return int_min

• Уловка-1: когда последнее значение массива находится в отрицательной области (после сортировки массива), это означает, что все элементы имеют отрицательное значение. Таким образом, вы можете вернуть 1 напрямую без каких-либо операций.
• Уловка-2: наименьшее значение среди положительных целых чисел равно 1. Если массив включает большее положительное значение, но не включает 1, возвращаемое значение равно 1 при обработке исключений.

Используйте приведенное выше решение для справки.
Я рекомендую вам написать собственный исходный код.

Связанный пост