剔除向量中的重复条目

Question

我有向量，我想检索一个包含所有条目的向量，这些条目在所有输入向量中的任何地方都没有重复。

#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)

}

是否有库函数可以帮助高效地执行此任务？

我不依赖于使用矢量。解决方案可以包括列表、集合或任何最适合任务的内容。

Answer 1

使用unordered_map，O(N) space 复杂度和 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;
}

剔除向量中的重复条目

Kick out duplicate entries across vectors

c++

unique