2

我正在尝试删除向量中的相同整数。我的目标是只有一个副本。好吧，我写了一个简单的代码，但它不能正常工作。任何人都可以帮忙吗？提前致谢。

#include <iostream>
#include <vector>
using namespace std;

int main()

{   

int a = 10, b = 10 , c = 8, d = 8, e = 10 , f = 6;
vector<int> vec;

vec.push_back(a);
vec.push_back(b);
vec.push_back(c);
vec.push_back(d);
vec.push_back(e);
vec.push_back(f);


for (int i=vec.size()-1; i>=0; i--)
{
    for(int j=vec.size()-1; j>=0; j--)
    {
        if(vec[j] == vec[i-1])
            vec.erase(vec.begin() + j);
    }
}   

for(int i=0; i<vec.size(); i++)
{
    cout<< "vec: "<< vec[i]<<endl;
}

return 0;
}
4

6 回答 6

3

不要为此使用列表。使用一组：

 #include <set>
 ...
 set<int> vec;

如果元素已经存在，这将确保您不会添加重复元素。

于 2013-10-18T17:08:56.193 回答
2

您的代码的问题在这里：

for(int j=vec.size()-1; j>=0; j--)
{
    if(vec[j] == vec[i-1])
        vec.erase(vec.begin() + j);
}

会有一段时间j==i-1，这会杀死你的算法，并且会有一段时间，i-1 < 0你会得到一个超出边界的异常。

你可以做的是改变你的 for 循环条件：

for (int i = vec.size() - 1; i>0; i--){
    for(int j = i - 1; j >= 0; j--){
        //do stuff
    }
}

这样，您比较的两个变量将永远不会相同，并且您的索引将始终至少为 0。

于 2013-10-18T17:12:40.047 回答
2

如果您需要保存数字的初始顺序，您可以使用辅助set<int>结构创建一个删除重复项的函数：

void removeDuplicates( vector<int>& v )
{
    set<int> s;
    vector<int> res;
    for( int i = 0; i < v.size(); i++ ) {
        int x = v[i];
        if( s.find(x) == s.end() ) {
            s.insert(x);
            res.push_back(x);
        }
    }
    swap(v, res);
}
于 2013-10-18T17:13:32.817 回答
2

其他人已经指出std::set。这当然简单易行——但它可能相当慢（比 慢很多std::vector，主要是因为（像链表一样）它由单独分配的节点组成，通过指针链接在一起形成平衡树1。

您可以（通常）通过使用 astd::unordered_set而不是 a 来改进它std::set。这使用哈希表2而不是树来存储数据，因此它通常使用连续存储，并给出 O(1) 预期访问时间而不是树预期的 O(log N)。

通常更快的替代方法是收集向量中的数据，然后对数据进行排序并用于std::unique消除重复项。当您有两个不同的操作阶段时，这往往是最好的：首先您收集所有数据，然后您需要删除重复项。如果您经常在添加/删除数据之间交替，并且需要一个重复的自由集，那么在std::set任何std::unordered_set时候都保持没有重复的集合可能更有用。

所有这些也会影响项目的顺序。std::set始终维护按定义顺序排序的项目。您需要对std::unique数据进行显式排序。您可以按照既不是原始顺序也不std::unordered_set是排序的任意顺序对项目进行排序。

如果您需要保持原始顺序但没有重复，则通常最终需要存储两次数据。例如，当您需要添加一个新项目时，您尝试将其插入到 中std::unordered_set，然后当且仅当成功时，也将其添加到向量中。

  1. 从技术上讲，作为树的实现并不是严格要求的，但这是我知道的唯一可以满足要求的可能性，并且我知道的所有实现都是基于树的。

  2. 同样，其他实现在理论上可能是可行的，但我知道所有这些都使用散列——但在这种情况下，暴露了足够多的实现，避免使用散列表可能会更加困难。

于 2013-10-18T17:28:57.097 回答
2

如果您首先对数组进行排序，则要删除重复项会更容易。下面的代码使用两种不同的方法来删除重复项：一种使用内置 C++ 算法，另一种使用循环。

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

int main() {
    int a = 10, b = 10 , c = 8, d = 8, e = 10 , f = 6;
    vector<int> vec;
    vec.push_back(a);
    vec.push_back(b);
    vec.push_back(c);
    vec.push_back(d);
    vec.push_back(e);
    vec.push_back(f);

    // Sort the vector
    std::sort(vec.begin(), vec.end());

    // Remove duplicates (v1)
    std::vector<int> result;
    std::unique_copy(vec.begin(), vec.end(), std::back_inserter(result));

    // Print results
    std::cout << "Result v1: ";
    std::copy(result.begin(), result.end(), std::ostream_iterator<int>(cout, " "));
    std::cout << std::endl;

    // Remove duplicates (v2)
    std::vector<int> result2;
    for (int i = 0; i < vec.size(); i++) {
        if (i > 0 && vec[i] == vec[i - 1])
            continue;
        result2.push_back(vec[i]);
    }

    // Print results (v2)
    std::cout << "Result v2: ";
    std::copy(result2.begin(), result2.end(), std::ostream_iterator<int>(cout, " "));
    std::cout << std::endl;

    return 0;
}
于 2013-10-18T17:30:12.447 回答
2

范围的主体不得更改它正在迭代的序列的大小。

您可以在 push_back 之前删除重复项

void push(std::vector<int> & arr, int n)
{

    for(int i = 0; i != arr.size(); ++i)
    {
        if(arr[i] == n) 
        {
            return;
        }
    }
    arr.push_back(n);
}

... ... 

push(vec, a);

push(vec, b);

push(vec, c);
...
于 2013-10-18T17:50:09.223 回答