Убрать все повторяющиеся элемента за O(n) времени?
используйте доп. структуру данных чтоб хранить кол-во вхождений каждого элемента в список. т.е. для каждого элемента в списке (сложность 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]
^ можете считать примером на псевдокоде, читатся вроде должно без проблем
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])
);
Тесты