c++ - 使用 std::map 从数组中删除重复项

Question

我将在 5 分钟内直接发布我在 collabedit 上编写的代码(包括弄清楚算法)，因此即使在效率方面存在完全取笑的风险，我想请教各位经验丰富的栈溢出算法爱好者；

基本上从数组中删除重复元素。 我的方法:基本上使用 std::map 作为我的哈希表，如果没有分配值，则将重复数组中的每个元素添加到我们的新数组中。如果分配只是跳过。最后返回唯一数组。这是我的代码，我唯一要问的面试问题是我的解决方案是否更有效？

#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<int>uniqueArr(int arr[],int size){
    std::map<int,int>storedValues;
    vector<int>uniqueArr;
    for(int i=0;i<size;i++){
        if(storedValues[arr[i]]==0){
            uniqueArr.push_back(arr[i]);
            storedValues[arr[i]]=1;
        }
    }
    return uniqueArr;  
}

int main()
{   
    const int size=10;
    int arr[size]={1,2,2,4,2,5,6,5,7,1};
    vector<int>uniArr=uniqueArr(arr,size);
    cout<<"Result: ";
    for(int i=0;i<uniArr.size();i++) cout<<uniArr[i]<<" ";
    cout<<endl;
    return 0;
}

Answer 1

首先，不需要映射，集合在概念上更正确，因为您不想存储任何值，而只想存储键。

性能方面，使用 std::unordered_set 而不是 std::set 可能是更好的主意，因为前者是散列的并且可以给出你在最好的情况下 O(1) 插入和查找，而后者是一个二叉搜索树，只给你 O(log n) 访问。

vector<int> uniqueArr(int arr[], int size)
{
    std::unordered_set<int> storedValues;
    vector<int> uniqueArr;
    for(int i=0; i<size; ++i){
        if(storedValues.insert(arr[i]).second)
            uniqueArr.push_back(arr[i]);
    return uniqueArr;  
}

但是如果你被允许更广泛地使用 C++ 标准库，你也可以考虑使用 std::sort 和 std::unique 的其他答案，尽管它们是O(n log n)(而不是上面的~O(n)解决方案)并且破坏了元素的顺序。

---

如果您想使用更灵活的标准驱动方法，但复杂度为 ~O(n) 并且不破坏元素的顺序，您可以将上述例程转换为以下类似标准的算法，即使是对于一个简单的面试问题来说有点牵强:

template<typename ForwardIterator>
ForwardIterator unordered_unique(ForwardIterator first, ForwardIterator last)
{
    typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
    std::unordered_set<value_type> unique;
    return std::remove_if(first, last, 
                          [&unique](const value_type &arg) mutable -> bool
                              { return !unique.insert(arg).second; });
}

然后您可以像 std::unique 一样以通常的删除-删除方式应用它:

std::vector<int> values(...);
values.erase(unordered_unique(values.begin(), values.end()), values.end());

在不复制 vector 且无需事先对其进行排序的情况下删除唯一值。