在 C++ 中查找向量的唯一元素

Question

有没有快速的方法来查找一个元素向量中所有只出现一次的单个元素？ 向量中的所有元素都是单个或双重（出现两次）。 我的答案是将所有元素排序，然后删除出现两次的元素。 有更快的方法吗？

- user1899020

---

如果允许额外的空间，我们可以构建一个以“单个元素”为键，“出现次数”为值的映射表，然后遍历该映射表，找到在你的情况下值应为1的单个元素。 - Yaman Jain

那么你想要的是一个集合而不是向量？ - user7287311

这些元素是什么类型？int、string还是用户定义的类型？ - P.W

你的输入预期大小是多少？你的向量保存了什么数据类型？你有任何内存限制吗？答案取决于所有这些因素，特别是第一个问题。 - unlut

输入数字的范围是多少？如果很小，比如你想从数组中找到介于1到100之间的唯一数字，那么你可以创建另一个数组，在索引位置上分配标志，例如seen[arr[i]]=1，然后遍历seen数组从1到100，然后打印所有元素，如果seen[i]为1。 - Mayur

Answer 1

因此，对于足够小的 n（<=1e8），排序和删除（使用 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<<" ";

- Photon

---

这是真的吗？在某个拐点上，使用哈希表比使用排序在时间上严格更好。根据定义，最佳性能取决于输入的大小（以及使用的哈希和排序算法）。 - Joel Cornett

@JoelCornett 是的，但实际上我们可能不会达到那个点，使用1e7个元素进行此操作仍然比哈希表更快，对于1e8个元素，哈希表已经需要太多内存才能适应我的RAM。 - Photon

使用布隆过滤器 ;) - Joel Cornett

没有问题。还有一个小细节，你甚至不能说1e8是绝对可行的。在实践中，“可能”是可行的，但它取决于元素的大小，以及页面大小和内存延迟。所有这些东西都可以在系统之间相当大地变化（例如嵌入式与服务器）。 - Joel Cornett

确切地说，虽然指出限制是好的，但要避免强加约束或在原始问题中没有要求的假设限制。 - David C. Rankin

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;
}

对于小列表，先排序再进行线性遍历可能仍然更快。同时请注意，这会复制你的元素，在某些情况下可能也很昂贵。

- Chemistree