Постановка задачи
Задав целочисленный массив nums, верните true, если любое значение встречается в массиве как минимум дважды, и верните false, если каждый элемент дублируется.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Подход 1 (грубая сила)
Давайте каждый раз выбирать элемент в массиве. Теперь посмотрим в оставшемся массиве, существует ли еще какой-нибудь элемент с таким же значением или нет. Если он существует, возвращаем true. В противном случае — false.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if nums[i] == nums[j]:
return True
return False
Временная сложность: O(n^2) — из-за вложенных циклов for.
Пространственная сложность: O(1).
Подход 2
Если мы отсортируем входной массив, то все дублирующиеся элементы будут расположены рядом друг с другом. Мы можем пройтись по массиву и проверить соседние элементы, одинаковые они или нет. Если найдена одна такая пара, можно вернуть true.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
for i in range(len(nums)-1):
if nums[i] == nums[i+1]:
return True
return False
Временная сложность: O(n log n) — из-за сортировки.
Пространственная сложность: O(1).
Подход 3
Давайте пройдемся итерациями по массиву и продолжим добавлять каждый элемент в хэшсет. При этом перед добавлением необходимо проверить, присутствует ли этот элемент в хэшсете. Эта операция проверки занимает O(1) времени, так как это хэшсет. Если мы нашли один такой элемент, мы можем вернуть true.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
hashSet = set()
for n in nums:
if n in hashSet:
return True
else:
hashSet.add(n)
return False
Временная сложность: O(n) — только один цикл for.
Пространственная сложность: O(n) — для дополнительного хэшсета.
Заключение
Сообщите мне, если я упустил какой-либо другой подход.
Следите за мной, чтобы получить больше подобных объяснений.
Давайте общаться на: Twitter LinkedIn Showwcase