Danil Sitdikov

используйте доп. структуру данных чтоб хранить кол-во вхождений каждого элемента в список. т.е. для каждого элемента в списке (сложность 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]

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