Содержит дубликат

Различные подходы к решению этой проблемы в JavaScript

Прежде чем мы углубимся в решения, давайте сначала подробно разберемся с постановкой задачи.

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

Подход 1:грубая сила

Сравните каждый элемент массива со всеми остальными элементами и проверьте, нет ли дубликатов.
Если мы находим дубликаты, мы возвращаем true; в противном случае мы возвращаем false.

// ES6 Arrow Function
const containsDuplicate = nums => {
  for(let i = 0; i < nums.length; i++) {
    for(let j = i+1; j < nums.length; j++) {
      if(nums[i] === nums[j]) return true;
    }
  }

  return false;
}

Временная сложность:O(N²)

Пространственная сложность:O(1)

Подход 2: Сортировка

Отсортируйте данный массив, а затем проверьте наличие дубликатов.
Если есть дубликаты, вернуть true; В противном случае верните false;

// ES6 Arrow Function
const containsDuplicate2 = nums => {
  nums.sort((a,b) => a-b);
  
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) return true;
  }

  return false;
}

Временная сложность:O(N * log(N))

Пространственная сложность:O(1)

Подход 3.Наборы

Создайте новый набор из значений входного массива.
Сравните длину входного массива и набора.
Отсутствие дубликатов означает, что длина массива и набора будут одинаковыми, верните false.
В противном случае вернуть true.

// ES6 Arrow Function
const containsDuplicate = nums => {
    const set = new Set(nums); 
    return set.size !== nums.length;
}

// Minified version
const containsDuplicate = nums => nums.length !== new Set(nums).size;

Временная сложность:O(N)

Пространственная сложность:O(N)

Подход 4.Карты

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

const containsDuplicate5 = nums => {
  let map = new Map();

  for(let i of nums) {
    if(map.has(i)) return true;
    map.set(i);
  }

  return false;
}

Временная сложность: O(N)

Пространственная сложность: O(N)

Примечание 1.Подход 4 также можно реализовать с помощью набора. Поэтому выбор подхода зависит от ваших предпочтений.

Примечание 2.При решении этой проблемы использование хеш-таблицы является лучшим подходом по сравнению со сравнением длины исходного входного массива и размера набора. Основным преимуществом хеш-таблицы является ее способность быстро определять результаты, в то время как использование набора требует добавления всех элементов перед сравнением его размера.

Я надеюсь, что эта статья предоставила вам ценную информацию и помогла вам лучше понять различные подходы к решению этой проблемы. Удачного кодирования!

Проблема - Leetcode 217

Содержит дубликат

Вопросы по теме