Убрать все повторяющиеся элемента за O(n) времени?

Question

[Danil Sitdikov]

Наткнулся на задачку

console.log(getUnique([2, 3, 4, 4]));//[2, 3]
console.log(getUnique([1, 2, 3, 4, 1, 4, 4, 0]));//[2, 3, 0]

Сделал ее так:

const getUnique = (arr) => arr.filter((it) => arr.filter((it2) => it2 === it).length < 2)

но в условии стояло именно O(n) алгоритм придумать и чет я залип

Comments

[Danil Sitdikov]

Пробовал несколько вариантов но везде выходила квадратичная сложность а нужна линейная

[Антон Федорян]

повторяющиеся элементы совсем отбрасываются?

[O . J]

используй Map

[Danil Sitdikov]

Антон Федорян, да полностью

Answer 1

[ayazer]

используйте доп. структуру данных чтоб хранить кол-во вхождений каждого элемента в список. т.е. для каждого элемента в списке (сложность O(n)) нужно увеличить счетчик в этой структуре данных (в случ. с хеш таблицой это O(n) в худшем и О(1) в среднем). и потом еще раз пройтись по хештаблице и достать с нее все элементы где счетчик = 1 (сложность O(n)). в итоге даже сложность для худшего случая будет o(n + n + n) = O(n)

те

var inputArray = new[] { 1, 2, 3, 4, 5, 4, 3, 2, 1 };
var set = new Dictionary<int, int>();

foreach (var val in inputArray)
{
    if (!set.ContainsKey(val))
    {
        set.Add(val, 1);
    }
    else
    {
        set[val] = set[val] + 1;
    }
}

var result = new List<int>();
foreach (var val in set)
{
    if (val.Value == 1)
    {
        result.Add(val.Key);
    }
}

return result; //[5]

^ можете считать примером на псевдокоде, читатся вроде должно без проблем

Comments

[Danil Sitdikov]

По итогу пришел к такому:

const removeNonUnique = array => {
  const dict = array.reduce((acc,it) => {
    if(acc[it]){
      acc[it] = {...acc[it], count: acc[it].count + 1}
      return acc
    }
    acc[it] = {value: it, count: 1}
    return acc
  }, {})

  return Object.keys(dict).filter((it) => dict[it].count < 2)
}

[Aves]

{...acc[it], count: acc[it].count + 1} это лишнее усложнение на пустом месте, которые ты не используешь - в итоге у тебя removeNonUnique([1, 2, 3, 4, 1, 4, 4, 0]) даёт ["0", "2", "3"] вместо [2, 3, 0], а надо ещё использовать map для извлечения value из acc.
Можно сделать проще:

function getUnique(arr) {
  const acc = {};
  for (const el of arr)
    acc[el] = acc[el] + 1 || 1;
  
  const res = [];
  for (const el of arr)
    if (acc[el] === 1)
      res.push(el);
      
  return res;
}

Answer 2

[Александр]

const removeNonUnique = array => {
    const cache = new Set();
    const store = new Set();

    for (const entry of array) {
        if (cache.has(entry)) {
            store.delete(entry);
        } else {
            cache.add(entry);
            store.add(entry);
        }
    }

    return [...store];
};

console.log(
    removeNonUnique([1, 2, 1, 1, 42, 3, 1, 3, 2, 3])
);

Тесты

Answer 3

[Danil Sitdikov]

Кому интересно то нашел такое решение:

const removeNonUnique = array => {
  const dict = array.reduce((acc,it) => {
    if(acc[it]){
      acc[it] = {...acc[it], count: acc[it].count + 1}
      return acc
    }
    acc[it] = {value: it, count: 1}
    return acc
  }, {})

  return Object.keys(dict).filter((it) => dict[it].count < 2)
}