Перейти к содержанию

Название задания

Ссылка с заданием на литкоде

Описание

Необходимо вернуть true если в nums любое число встречается хотя бы два раза, если все числа уникальные вернуть false.

Пример 1:

Входные данные: nums = [1, 2, 3, 1]
Выходные данные: true
Объяснение: число 1 встречается два раза в nums

Пример 2:

Входные данные: nums = [1, 2, 3, 4]
Выходные данные: false

Пример 3:

Входные данные: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Выходные данные: true

Идея решения

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

Зная, что множества позволяют хранить только уникальные значения мы можем привести наш массив чисел к множеству и сравнить их длину. В большинстве языков программирования метод получения длины работает за константное время, поскольку значение длины является атрибутом объекта. Учитывая эти две особенности и то, что проверка вхождения элемента в множество так-же выполняется за константное время, можно оптимизировать именно часть с приведением к множеству и возвращать ответ при получении первого дупликата.

Алгоритм решения

Во время иттерации по числам мы можем добавлять их в множество/хэш-таблицу. Если текущее число уже есть в нашей структуре данных, то можно сразу вернуть ответ true из функции.

Таким образом наш алгоритм выглядит так: 1. создаём структуру storage для хренения значений по их хешу 2. итерируемся по массиву 3. если ранее встречали текущее число - возвращаем true из функции, иначе добавляем его в storage 4. при завершении итерации возвращаем false, поскольку деблей не было

Сложность

  • По времени: \(O(N)\) n = len(nums) Мы итерируемся по всем элементам массива один раз. При этом если функция возвращает true, то нам потребуется проверить меньше чем n чисел.

  • По памяти: \(O(N)\) n = len(set(nums)) Для работы данного алгоритма необходима дополнительная память для хранения уникальных значений из входного массива. В худшем случае, когда функция возвращает false длина множества будет равна длине входного массива.

Код решения:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        storage = set()
        for num in nums:
            if num in storage:
                return True
            else:
                storage.add(num)
        return False

use std::collections::HashSet;

impl Solution {
    pub fn contains_duplicate(nums: Vec<i32>) -> bool {
        let mut set: HashSet<i32> = HashSet::new();
        for number in nums {
            if set.contains(&number) {
                return true;
            } else {
                set.insert(number);
            }
        }
        false
    }
}