Как очистить массив от повторяющихся элементов?

Question

[asmodeus13th]

Суть вопроса. Написать функцию, которая принимает массив и возвращает массив с элементами, которые не повторялись. Массив может состоять из чисел, строк и логических типов. Скорость работы функции должна быть не более О(n).
Результат. Передаю в функцию [2, 5, 8, 2, true, 5, 2] и получаю [8, true].

Comments

[WbICHA]

freelance.habr.com

[Kovalsky]

Вы не ошиблись в результате? Конкретно в выходном массиве

[asmodeus13th]

Kovalsky, 2 и 5 - повторяющиеся элементы. 8 и true - только в одном экземпляре. Всё верно.

[asmodeus13th]

Kovalsky, аналогично [1, 2, 1, 1, 1, 1] => [2].

[Kovalsky]

asmodeus13th, а, прям вообще от всех у которых есть дубли, не от самих дублей, понятно. Ну тогда алгоритм наверное такой: найти все повторяющиеся, удалить их из исходного массива

[asmodeus13th]

WbICHA, Вы отправляете меня в другой форум с вопросами? Зачем? Задать вопрос? Это простая задача. Я решил её, но скорость выполнения кода О(n^n), а это очень долго. Так массив из 3 элементов выполняется О(18).

[asmodeus13th]

Kovalsky, вы предлагает сделать цикл в цикле. Это занимает О(n^n) времени, а надо снизить время хотя бы до О(n).

[asmodeus13th]

Kovalsky, лучшее, до чего я додумался: создать словарь, где ключ - элемент, а значение - кол-во повторений. Потом отфильтровать словарь от значений больше 1. Это занимает O(n*n) времени. Это лучше, но тоже долго.

[Kovalsky]

asmodeus13th, можно ещё отфильтровать только те значения, для которых будут равны indexOf и lastIndexOf, но мне кажется подкапотная сложность алгоритма будет больше O(n), потому что может быть на верхнем уровне (на уровне JS) это будет и один цикл, но внутри будет еще n циклов, хотя я не разбираюсь в таком

Даже в ноде метод выглядит лютенько

[asmodeus13th]

Kovalsky, да, Вы правы!

[asmodeus13th]

Хочу показать пример выполнения задания. Скорость функции О(nⁿ), так как на каждый элемент в цикле приходится ещё один цикл.

function uniqueArr(arr){
  /**
   * Принимает массив и возвращает его уникальные значения.
   */

  const accumulate = [];  // сохраняет уникальные значения

  for (let foo of arr){
    let count = 0; // счётчик для повторяющихся элементов

    for (let bar of arr){
      if (foo === bar) count++; // кол-во повторяющихся элементов
    }

    if (count === 1){
      // если значение в массиве только одно,
      // добавляет это значение в конечный массив
      accumulate.push(foo);
    }
  }

  return accumulate
}

Answer 1

[0xD34F]

Собрать новый массив:

const newArr = Array
  .from(arr.reduce((acc, n) => acc.set(n, (acc.get(n) ?? 0) + 1), new Map))
  .filter(n => n[1] === 1)
  .map(n => n[0]);

Обновить существующий:

arr.splice(0, arr.length, ...Array
  .from(arr.reduce((acc, n) => acc.set(n, acc.has(n)), new Map))
  .reduce((acc, n) => (n[1] || acc.push(n[0]), acc), [])
);

Comments

[asmodeus13th]

Вы очень сильно усложняете. Скорость такого кода O(n^3n). Это намного дольше, чем использование цикл в цикле из уроков для новичков.
Ещё одни важный нюанс - обернуть код в функцию. Это не проблема, просто задание - написать функцию.

[asmodeus13th]

Ещё хочу добавить, что Ваш код было сложно читается. Проблема не в методах, а в отсутствии комментариев и банальной логики. В остальном всё по классике. Даже переменные названы по негласному стандарту.

[0xD34F]

asmodeus13th,

Скорость такого кода O(n^3n)

Ну, давайте, расскажите, откуда вы это взяли.

Ещё одни важный нюанс - обернуть код в функцию.

Разрешаю вам сделать это самостоятельно.

Это не проблема, просто задание...

С заданиями - на фриланс. Платите деньги - вам делают.

[Дмитрий Беляев]

asmodeus13th, где Вы тут увидели O(n³)? От того, что по массиву пробежались несколько раз сложность не меняется, и здесь она линейная O(n)

[Алексей]

Дмитрий Беляев, какая сложность у такого редюса ?

[1,1,2,3,4,5,5,6,6,6,6,6,4,1,6,7].reduce((acc, item, i, arr) => {
	if (acc.has(item)) return acc;
	let idx = arr.indexOf(item);
	let lastIdx = arr.lastIndexOf(item);
	if (idx === lastIdx) {
		acc.add(item);
	};
	return acc;
}, new Set());

[asmodeus13th]

0xD34F, Дмитрий Беляев,
Ответ к измерении скорости:
я могу с таким успехом 1000 раз пробежаться по массиву и сказать, что скорость линейная. Это не так. Читайте книжки)

Разрешаю вам сделать это самостоятельно.

Тогда Ваш ответ не может быть ответом к вопросу. С такой логикой, можно сделать ответом комментарий: "Загугли"!

С заданиями - на фриланс

Не рекомендую придираться к словам. Вы поняли, что я имел ввиду.

Хочу подвести итоги. В споре рождаются решения. Помните, что сюда приходят и новички с "глупыми" вопросами. Относитесь с пониманием и помогайте друг-другу. Вместо того, чтобы доказывать, что я дурак, лучше приложите усилие на решение задачи или просто проигнорируйте заданный вопрос и не пишите "важное" мнение.

[asmodeus13th]

Дмитрий Беляев,

по массиву пробежались несколько раз сложность не меняется

После этих слов, дальнейшие Ваши комментарии не стоят внимания. О-большое измеряет не сложность, а скорость.

[0xD34F]

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

[WbICHA]

asmodeus13th,

я могу с таким успехом 1000 раз пробежаться по массиву и сказать, что скорость линейная. Это не так. Читайте книжки)

Незнание и непонимание базовых вещей вкупе с огромным ЧСВ выдают невероятных персонажей.)

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

0xD34F выкладывает стандартное решение с использованием базовых вещей современного жса с соблюдением всех основных требований.
Ваш ответ:

Скорость такого кода O(n^3n). (ложь)
Это намного дольше, чем использование цикл в цикле из уроков для новичков. (отсутствие логического мышления)
просто задание - написать функцию. (а это сайт "ответы на вопросы", а не "решение задач")
Ваш код было сложно читается. (допустим, я бы мог согласиться если бы не...)
Проблема ... в отсутствии комментариев и банальной логики. (...вот этот бред, особенно про комментарии, которые в коде должны быть только в исключительных случаях)

Приходит первоклассник в университет и начинает учить профессоров.

[asmodeus13th]

WbICHA, мда… Я ожидал многого, но настолько перекрутить всё…

с соблюдением всех основных требований.

Я же в комментарии выше повторил, что мне нужна функция, повторил о скорости и многое другое. Снова писать я не стану. Ваш комментарий не является ответом на вопрос, а значит не уместен.

непонимание базовых вещей

Самокритично.

[WbICHA]

asmodeus13th, всё, я понял, ты тролль. Это многое объясняет.

[Дмитрий Беляев]

какая сложность у такого редюса ?

[1,1,2,3,4,5,5,6,6,6,6,6,4,1,6,7].reduce((acc, item, i, arr) => {
  if (acc.has(item)) return acc;
  let idx = arr.indexOf(item);
  let lastIdx = arr.lastIndexOf(item);
  if (idx === lastIdx) {
    acc.add(item);
  };
  return acc;
}, new Set());

Алексей, сам reduce - O(n), внутри него indexOf и lastIndexOf по тому же массиву, оба с O(n), максимальная - O(n), так как у нас вложенные вычисления (на каждую итерацию внешнего полный цикл внутренних), то сложности перемножаются - O(n²)

[Дмитрий Беляев]

После этих слов, дальнейшие Ваши комментарии не стоят внимания. О-большое измеряет не сложность, а скорость.

asmodeus13th, О-большое измеряет асимптотическую сложность алгоритма в худшем случае (включая этот худший случай, o-малое соответственно не включая)
Ω-большое измеряет асимптотическую сложность алгоритма в лучшем случае (включая этот лучший случай, ω-малое соответственно не включая)
асимптотическая сложность алгоритма исследует по какой функции растут вычислительные затраты при росте числа элементов. Если Вы пробежитесь по массиву 1000 раз, рост останется линейным (на 1 элемент было 1000 вычислений, на 2 - 2000 вычислений, на 3 - 3000 вычислений, на 1000 элементов - 1 млн вычислений, на 1 млн элементов - 1 млрд вычислений), а значит O(1000n) == O(n)
А вот если циклы вложены, то рост будет квадратичным (на 1 элемент - 1 вычисление, на 2 элемента - 4 вычисления, на 3 элемента - 9 вычислений, на 1000 элементов будет 1 млн вычислений, на 1 млн элементов - 1 трлн вычислений)

А такого понятия, как скорость алгоритма не существует. Один и тот же фрагмент кода может выполнятся с разной производительностью в зависимости от такого огромного количества факторов, что даже предсказание его скорости выполнения становится нерешаемой задачей, не говоря уж о точных вычислениях

Answer 2

[aloky]

new Set?

Comments

[asmodeus13th]

Вы не поняли вопрос. Массив [1,2,1,1,1,1] должен превратиться в [2], new Set вернёт [1,2].