Код
#статьи

Задача: проверить массив на дубликаты

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня ищем в массиве повторяющиеся элементы.

Иллюстрация: Polina Vari для Skillbox Media

Сергей Голицын


Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.


Условие. Дан массив целых чисел — nums. Необходимо написать функцию, которая возвращает true, если в этом массиве хотя бы одно число повторяется дважды. Если же все элементы уникальны, функция должна вернуть false.

Ввод и вывод. Пример 1

Ввод: nums = [1,2,3,1]
Вывод: true

Пример 2

Ввод: nums = [1,2,3,4]
Вывод: false

Пример 3

Ввод: nums = [1,1,1,3,3,4,3,2,4,2]
Вывод: true

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

При решении подобных задач важно выбрать подходящий тип данных. Здесь мы исходим из такой логики: «повторяется дважды» → значит, ищем дубликаты. Следовательно, выбираем множество (set).

Мы создадим пустое множество и будем обходить весь массив, просто проверяя, находится ли элемент во множестве:

  • если он ещё не находится — добавляем его;
  • если элемент уже там — значит, мы встретили повторяющийся элемент и просто возвращаем true.
public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int i : nums) {
        if (set.contains(i)) {
            return true;
        } else {
            set.add(i);
        }
    }
    return false;
}

Результаты

Временная сложность: O(n) — так как в самом плохом случае мы проходимся по всему массиву.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.


Жизнь можно сделать лучше!
Освойте востребованную профессию, зарабатывайте больше и получайте от работы удовольствие.
Каталог возможностей
Понравилась статья?
Да

Пользуясь нашим сайтом, вы соглашаетесь с тем, что мы используем cookies 🍪

Ссылка скопирована