0

我直接发布了我在 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;
}
4

4 回答 4

4

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

std::unordered_set在性能方面，使用 a而不是 a可能是一个更好的主意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::sortand的其他答案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());

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

于 2012-06-09T23:08:13.690 回答
2

既然你问的是面试问题，我会说你没有得到这份工作。

const int size=10;
int arr[size]={1,2,2,4,2,5,6,5,7,1};

std::sort( &arr[0], &arr[size] );
int* new_end = std::unique( &arr[0], &arr[size] );

std::copy(
    &arr[0], new_end,
  , std::ostream_iterator< int >( std::cout, " " )
);

没有临时映射，没有临时向量，没有动态内存分配，编写的代码少得多，因此更容易编写和维护。

于 2012-06-09T22:52:06.540 回答
1 
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> vec({1,2,3,2,4,4,5,7,6,6});
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    // vec = {1,2,3,4,5,6,7}
    return 0;
}
//works with C++11
// O(n log n)
于 2012-06-09T23:05:42.520 回答
1

就地移除对速度很有好处 - 像这样（返回新大小）：

template <typename T, size_t N>
size_t keep_unique(T (&array)[N])
{
    std::unordered_set<T> found;
    for (size_t i = 0, j = 0; i < N; ++i)
        if (found.insert(array[i]).second))
            if (j != i) // (optional) avoid copy to self, as may be slower or unsupported by T
                array[j++] = array[i];
            else
                ++j;
    return j;
}

（对于较大的对象或无法安全复制的对象，可能需要和/或更快且更节省空间来将T*s 存储在 unordered_set 中 - 还必须提供取消引用比较运算符和散列函数。）

为了可视化这是如何工作的，请考虑处理以下输入：

1  3  6  3  5  6  0  2  1
         <--+<----+  |
               <-----+

上面的箭头表示产生答案所需的最小就地压缩：

1  3  6  5  0  2

这正是上面的算法所做的，查看 中的所有元素[i]，并跟踪它们需要复制到的位置（以及有多少非重复项）[j]。

于 2012-06-11T07:03:38.010 回答