Сегодня я вам предлагаю немного снизить темп и в последний рабочий день недели посмотреть на очень простую классическую задачу.
Сложность: 🟢 Легкая
ℹ️ Описание
Дан целочисленный массив. Напишите функцию, которая принимает на вход массив и возвращает true, если какое-либо значение встречается в массиве более одного раза. Если каждое значение в массиве уникально, то функция должна возвращать false.
⚠️ Ограничения
🔹 В массиве может быть от 1 до 105 элементов
🔹 Каждое значение может быть в диапазоне от -109 до 109
1️⃣Пример
Входящие данные
[1, 2, 3, 1]
Ответ
true
2️⃣Пример
Входящие данные
[1, 2, 3, 4]
Ответ
false
✅ Решение через Hash Map
Для решения задачи этим способом достаточно проитерироваться по всем элементам массива. На каждой итерации нужно подсчитывать количество значений, которые встречаются. Для этого можно использовать Map:
▶️если в мапе не существует такого значения, то мы добавляем его туда и переходим к следующей итерации;
▶️если в мапе уже есть такое значение, то мы прерываем функцию и возвращаем true.
Посмотреть решение в блоге
🅾️ Оценка сложности
Сложность по времени
Сложность O(n), где n — количество элементов в массиве, так как в худшем случае мы пройдем в цикле по всем элементам.
Сложность по памяти
Сложность O(n), так как мы выделяем мапу для хранения частот значений.
✅ Решение через сортировку
Для решения задачи этим способом достаточно необходимо предварительно отсортировать массив в любом порядке. Так как в отсортированном массиве одинаковые значения всегда находятся рядом, нам будет достаточно пройти по всем элементам массива и вернуть true, если мы встретим два одинаковых значения рядом.
Посмотреть решение в блоге
🅾️ Оценка сложности
Сложность по времени
Сложность алгоритма равна сложности сортировки, так как она больше линейной — O(n * logn).
Сложность по памяти
Сложность O(1), так как мы не выделяем дополнительной памяти.
#easy #arrays