Удалять повторяющиеся записи через векторы

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

#include <vector> 
int main() { 

    std::vector<int> a = {2, 1, 3}; 
    std::vector<int> b = {99, 1, 3, 5, 4}; 
    std::vector<int> c = {5, 6, 7, 1}; 

    // magic to retrieve {2, 99, 4, 6, 7} (order doesn't matter) 

}

Есть ли функция библиотеки, которая может эффективно выполнять эту задачу?

Я не привязан к использованию векторов. Решение может включать в себя списки, наборы или все, что наиболее подходит для задачи.

источник

2015-06-19 Nico Schlömer

Это не решает задачу. Если запись появляется несколько раз, я хотел бы, чтобы она полностью ударила ногой. –

Вы не сказали, нормально ли использовать O (N) пространство для этой задачи ok. Если это нормально, вы можете сначала поместить все элементы в unorderd_map сначала, а затем элемент, который имеет число count equl до 1, помещенное в vector –

@Nico Schlömer Почему 99 в последовательности результатов отсутствует? –

Используя unordered_map, O (N) пространство сложность и O (N) временная сложность:

#include <vector> 
#include <unordered_map> 
#include <iostream> 

std::vector<int> 
get_unique_values(std::initializer_list<std::vector<int>> vectors) 
{ 
    std::unordered_map<int, size_t> tmp; 
    auto insert_value_in_tmp = [&tmp](int v) { 
    auto i = tmp.find(v); 
    if (i == tmp.end()) 
     tmp[v] = 1; 
    else if (i->second != 2) 
     i->second = 2; 
    }; 

    for (auto& vec : vectors) { 
    for (auto vec_value : vec) { 
     insert_value_in_tmp(vec_value); 
    } 
    } 

    std::vector<int> result; 
    for (auto v : tmp) { 
    if (v.second == 1) 
     result.push_back(v.first); 
    } 

    return result; 
}; 

int main() { 

    std::vector<int> a = {2, 1, 3}; 
    std::vector<int> b = {99, 3, 5, 4}; 
    std::vector<int> c = {5, 6, 7}; 

    std::vector<int> result = get_unique_values({a,b,c}); 

    for (auto v : result) { 
    std::cout << v << " "; 
    } 
    std::cout << '\n'; 

    return 0; 
}

источник

2015-06-19 21:20:34

Удалять повторяющиеся записи через векторы

ответ

Смежные вопросы