Найти уникальные элементы вектора C ++

Question

Существует ли быстрый способ найти все отдельные элементы (только один раз) в векторе элементов? Все элементы вектора являются одинарными или двойными (появляются дважды). Мой ответ - отсортировать все элементы, а затем удалить дважды появившиеся элементы. Есть ли более быстрый способ сделать это?

Answer 1

Таким образом, при достаточно малом n (<= 1e8) подходе сортировки и удаления (с использованием <code>std::sort() и std::unique) подход все еще быстрее, чем хеш-таблиц.

Пример кода: O (n log n)

vector<int>A = {1,2,3,1,2,5};
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    for(int&x:A)
        cout<<x<<" ";

Answer 2

если ваши элементы могут быть хэшируемыми, вы можете использовать std::unordered_map<T, int> для хранения счетчика каждого элемента, который будет занимать амортизированное линейное время:

template<typename T>
std::vector<T> uniqueElements(const std::vector<T>& v) {
    std::unordered_map<T, int> counts;
    for(const auto& elem : v) ++counts[elem];
    std::vector<T> result;
    for(auto [elem, count] : counts)
        if(count == 1)
            result.push_back(elem);
    return result;
}

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