Contains Duplicate

Q: Какова временная сложность задачи Contains Duplicate?

Решение с хеш-множеством работает в среднем за время O(n) и использует дополнительную память объёмом O(n) . Предварительная сортировка занимает время O(n log n) и не требует дополнительного массива, если входные данные можно переупорядочить. Сравнение каждой пары занимает время O(n²) .

Q: Можешь решить задачу «Содержит дубликаты» без дополнительного пространства?

Да, если тебе разрешено менять порядок элементов массива: отсортируй его на месте и сравни каждое значение с соседним. Так ты заменишь множество за O(n) на время O(n log n) . Если нельзя менять порядок и использовать дополнительную память, остаётся только проверка пар за O(n²) .

Q: Почему хеш-множество позволяет быстро выполнять проверку?

Хеш-множество хранит значения по их хешам, поэтому проверка наличия значения в среднем занимает постоянное время, а не требует перебора. Для каждого элемента выполняется один поиск и одна вставка, поэтому весь проход занимает линейное время.

Q: Сравнение размера множества с длиной массива — допустимое решение?

Да. Создание множества из всего массива nums и проверка, меньше ли оно массива, дают правильный ответ за время O(n) . Вариант с циклом часто лучше, потому что он возвращает результат сразу после обнаружения первого повтора, тогда как при создании всего множества всегда считываются все значения.

ЛегкоХеширование

+10

Дан массив целых чисел nums. Верните true, если какое-либо значение встречается в нём как минимум дважды, и false, если все значения различны.

Функция

containsDuplicate(nums: integer-array) → boolean

numsinteger-array: целые числа для проверки
Возвращаетboolean: true, если какое-либо значение встречается не менее двух раз, в противном случае — false

Ограничения

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Примеры

Ввод: nums = [3, 1, 4, 1, 5]
Вывод: true
Пояснение: Значение 1 находится по индексу 1 и снова по индексу 3, поэтому ответ — true.

Ввод: nums = [2, 7, 1, 8]
Вывод: false
Пояснение: 2, 7, 1 и 8 — это четыре разных значения, поэтому ничего не повторяется.

Ввод: nums = [-4, 4, 0]
Вывод: false
Пояснение: -4 и 4 имеют одинаковое абсолютное значение, но это разные числа, а 0 встречается один раз, поэтому ответ — false.

+17 скрытых тестов при отправке

Дополнительный вопрос

Можешь остановиться, как только встретишь первое повторяющееся значение, вместо того чтобы всегда читать весь массив?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Повтор — это значение, которое вы уже встречали, и задача состоит в том, чтобы быстро ответить на вопрос: «Я уже встречал это значение?». Сравнение каждой пары позволяет ответить на него, но при n = 10^4 это n(n-1)/2, то есть примерно 5 × 10^7 сравнений. Сортировка ставит одинаковые значения рядом друг с другом, а хеш-множество в среднем отвечает на этот вопрос за O(1), что позволяет выполнить один проход.

Отсортируйте, затем сравните соседние элементы

Идея

В отсортированном массиве одинаковые значения стоят рядом. [3, 1, 4, 1, 5] сортируется в [1, 1, 3, 4, 5], и две 1 теперь соприкасаются. Поэтому после сортировки нужно сравнить каждое значение только со значением непосредственно перед ним: n-1 сравнений вместо n(n-1)/2, которые нужны, чтобы проверить каждую пару.

Если никакие два соседних элемента не равны, значит, нигде в массиве нет двух одинаковых значений: любое значение между двумя копиями x в отсортированном порядке должно быть одновременно не меньше x и не больше x, то есть оно тоже должно быть равно x.

Основную часть времени занимает сортировка: O(n log n). Сортировка nums на месте не требует дополнительного массива, но меняет порядок элементов во входных данных вызывающего кода; если это недопустимо, отсортируй копию, на что потребуется O(n) дополнительной памяти.

Алгоритм

Отсортируй nums по возрастанию.
Перебирай i от 1 до последнего индекса.
Если nums[i] равно nums[i-1], верни true.
После цикла верни false.

def containsDuplicate(nums):
    nums.sort()
    # After sorting, equal values sit next to each other.
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Один проход с хеш-множеством

Идея

Один раз пройдись по массиву и сохраняй в хеш-множество каждое уже встреченное значение. Перед добавлением значения проверь, есть ли оно уже в множестве. Для [3, 1, 4, 1, 5] множество разрастается до {3, 1, 4}, и когда появляется вторая 1, она уже есть в множестве, поэтому верни true, не читая 5.

Множество всегда содержит в точности значения, расположенные до текущей позиции, поэтому совпадение означает, что текущее значение встречалось раньше, а если дойти до конца без совпадений, значит, все значения различны.

Поиск и вставка в хеш-множество в среднем занимают время O(1), поэтому весь проход занимает O(n). Цена за это — память: если повторов нет, в итоге множество будет содержать все n значений.

Алгоритм

Создай пустое хеш-множество seen.
Для каждого значения в nums, если оно содержится в seen, верни true.
Иначе добавь его в seen.
После цикла верни false.

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Ловушки и крайние случаи

Логика проста, поэтому ошибки связаны с границами циклов и тем, что вы сравниваете.

Сравнение каждой пары, когда внутренний цикл начинается с j = i. Тогда каждое значение совпадает само с собой, и ответ всегда равен true.
Сравнение соседних элементов без предварительной сортировки. В [9, 1, 2, 3, 9] две 9 не стоят рядом.
Начало цикла по соседним элементам с индекса 0 и чтение nums[-1]. Начните с 1, и массив из одного значения правильно вернёт false.
Считать значения с одинаковым абсолютным значением равными, например, используя хеширование abs(x). -4 и 4 — разные числа.
Написание компаратора сортировки в C, который возвращает x - y. Здесь разность остаётся в пределах ±2 × 10^9, что меньше предела типа int 2^31-1 = 2147483647, поэтому в данном случае она помещается; для значений, близких к пределам int, происходит переполнение, и сортировка выполняется неправильно. Вместо этого возвращайте (x > y) - (x < y).

Частые вопросы4

Какова временная сложность задачи Contains Duplicate?

Решение с хеш-множеством работает в среднем за время O(n) и использует дополнительную память объёмом O(n). Предварительная сортировка занимает время O(n log n) и не требует дополнительного массива, если входные данные можно переупорядочить. Сравнение каждой пары занимает время O(n²).

Можешь решить задачу «Содержит дубликаты» без дополнительного пространства?

Да, если тебе разрешено менять порядок элементов массива: отсортируй его на месте и сравни каждое значение с соседним. Так ты заменишь множество за O(n) на время O(n log n). Если нельзя менять порядок и использовать дополнительную память, остаётся только проверка пар за O(n²).

Почему хеш-множество позволяет быстро выполнять проверку?

Хеш-множество хранит значения по их хешам, поэтому проверка наличия значения в среднем занимает постоянное время, а не требует перебора. Для каждого элемента выполняется один поиск и одна вставка, поэтому весь проход занимает линейное время.

Сравнение размера множества с длиной массива — допустимое решение?

Да. Создание множества из всего массива nums и проверка, меньше ли оно массива, дают правильный ответ за время O(n). Вариант с циклом часто лучше, потому что он возвращает результат сразу после обнаружения первого повтора, тогда как при создании всего множества всегда считываются все значения.

Python

def containsDuplicate(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [3, 1, 4, 1, 5]

Ожидается

true