@QuadradS

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

Наткнулся на задачку
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) алгоритм придумать и чет я залип
  • Вопрос задан
  • 192 просмотра
Решения вопроса 2
ayazer
@ayazer
Sr. Software Engineer
используйте доп. структуру данных чтоб хранить кол-во вхождений каждого элемента в список. т.е. для каждого элемента в списке (сложность 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]

^ можете считать примером на псевдокоде, читатся вроде должно без проблем
Ответ написан
Seasle
@Seasle Куратор тега JavaScript
\( ゚ヮ゚)/
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])
);

Тесты
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@QuadradS Автор вопроса
Кому интересно то нашел такое решение:
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)
}
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы