Проверка массива на дубликаты
Описание задачи #
Дан целочисленный массив.
Напишите функцию, которая принимает на вход массив и возвращает true, если какое-либо значение встречается в массиве более одного раза.
Если каждое значение в массиве уникально, то функция должна возвращать false.
Ограничения #
- В массиве может быть от 1 до 105 элементов
- Каждое значение может быть в диапазоне от -109 до 109
Примеры #
-
Входные данные:
[1, 2, 3, 1]Ответ:
true -
Входные данные:
[1, 2, 3, 4]Ответ:
false
Решение через Hash Map #
Для решения задачи этим способом достаточно проитерироваться по всем элементам массива.
На каждой итерации нужно подсчитывать количество значений, которые встречаются.
Для этого можно использовать структуру Hash Map:
- если в мапе не существует такого значения, то мы добавляем его туда и переходим к следующей итерации;
- если в мапе уже есть такое значение, то мы прерываем функцию и возвращаем
true.
-
package main func containsDuplicateWithMap(nums []int) bool { frequency := make(map[int]bool) for _, num := range nums { _, exists := frequency[num] if exists { return true } frequency[num] = true } return false } -
export const containsDuplicateWithMap = (nums: number[]): boolean => { const frequency: Map<number, boolean> = new Map() for (let i = 0; i < nums.length; i++) { const num = nums[i] if (frequency.has(num)) { return true } frequency.set(num, true) } return false }
Оценка сложности #
По времени
Сложность O(n), где n — количество элементов в массиве, так как в худшем случае мы пройдем в цикле по всем элементам.
По памяти
Сложность O(n), так как мы выделяем мапу для хранения частот значений.
Решение через сортировку #
Для решения задачи этим способом необходимо предварительно отсортировать массив в любом порядке.
Так как в отсортированном массиве одинаковые значения всегда находятся рядом, нам будет достаточно пройти по всем элементам массива и вернуть true, если мы встретим два одинаковых значения рядом.
-
package main import "sort" func containsDuplicateWithSort(nums []int) bool { sort.Ints(nums) for i := 0; i < len(nums)-1; i++ { if nums[i] == nums[i+1] { return true } } return false } -
export const containsDuplicateWithSort = (nums: number[]): boolean => { nums.sort() for (let i = 0; i < nums.length - 1; i++) { if (nums[i] === nums[i + 1]) { return true } } return false }
Оценка сложности #
По времени
Сложность алгоритма равна сложности сортировки, так как она больше линейной — O(n * logn).
По памяти
Сложность O(1), так как мы не выделяем дополнительной памяти.