如何删除排序向量中的重复项
我目前有一个vector<int> c其中包含{1,2,2,4,5,5,6}
，我想删除重复的数字，以便c将
{1,4,6}. 互联网上的许多解决方案似乎只是删除了其中一个重复项，但我正在尝试删除所有出现的重复号码。
假设c总是排序的。
我目前有
#include <iostream>
#include <vector>
int main() {
vector<int> c{1,2,2,4,5,5,6};
for (int i = 0; i < c.size()-1; i++) {
for (int j=1; j<c.size();j++){
if(c[i] == c[j]){
// delete i and j?
}
}
}
}
我尝试使用两个 for 循环，以便可以比较当前元素和下一个元素。这就是我怀疑的地方。我不确定我是否正确地解决了这个问题。
我能否就如何解决我的问题获得帮助？
回答
这段代码基于这样一种认识，即一个元素在排序列表中是唯一的，当且仅当它与紧邻它的两个元素不同（除了开始和结束元素，它们都与一个元素相邻）。这是真的，因为所有相同的元素必须在排序数组中相邻。
void keep_unique(vector <int> &v){
if(v.size() < 2){return;}
vector <int> unique;
// check the first element individually
if(v[0] != v[1]){
unique.push_back(v[0]);
}
for(unsigned int i = 1; i < v.size()-1; ++i){
if(v[i] != v[i-1] && v[i] != v[i+1]){
unique.push_back(v[i]);
}
}
// check the last item individually
if(v[v.size()-1] != v[v.size()-2]){
unique.push_back(v[v.size()-1]);
}
v = unique;
}
回答
几乎任何时候您发现自己从向量的中间删除元素时，最好坐下来思考这是否是完成这项工作的最佳方法 - 机会很好，但它不是。
有几个明显的替代方案。一种是将要保留的项目复制到临时向量中，然后在完成后交换临时向量和原始向量。这在您在问题中显示的情况下特别有效，您只保留了相当少的输入数据。
另一种方法是重新排列现有向量中的数据，使您不想要的所有数据都在末尾，而您想要的所有数据都在开头，然后调整向量的大小以消除您不想要的数据。
当我怀疑时，我倾向于走第一条路。从理论上讲，它可能效率较低（参考位置较差），但我很少看到实际使用中的显着放缓。
既然如此，我最初的看法可能是按照这个一般顺序进行的：
#include <vector>
#include <iostream>
#include <iterator>
std::vector<int> remove_all_dupes(std::vector<int> const &input) {
if (input.size() < 2) // zero or one element is automatically unique
return input;
std::vector<int> ret;
// first item is unique if it's different from its successor
if (input[0] != input[1])
ret.push_back(input[0]);
// in the middle, items are unique if they're different from both predecessor and successor
for (std::size_t pos = 1; pos < input.size() - 2; pos++)
if (input[pos] != input[pos-1] && input[pos] != input[pos+1])
ret.push_back(input[pos]);
// last item is unique if it's different from predecessor
if (input[input.size()-1] != input[input.size()-2])
ret.push_back(input[input.size() - 1]);
return ret;
}
int main() {
std::vector<int> c { 1, 2, 2, 4, 5, 5, 6 };
std::vector<int> uniques = remove_all_dupes(c);
std::copy(uniques.begin(), uniques.end(), std::ostream_iterator<int>(std::cout, "n"));
}
代码可能比我们真正喜欢的要长一点，但仍然简单、直接且高效。
如果您打算就地完成这项工作，通常有效的方法（这适用于一般过滤，而不仅仅是这个特定过滤器）是从复制阶段开始，然后是删除阶段。在复制阶段，您使用两个指针：源和目标。您从第一个元素开始它们，然后使用源在输入中前进。如果它符合您的标准，则将其复制到目标位置，并同时推进两者。如果它不符合您的标准，请仅推进源。
然后，当您完成此操作后，将向量调整为您保留的元素数量。
void remove_all_dupes2(std::vector<int> & input) {
if (input.size() < 2) { // 0 or 1 element is automatically unique
return;
}
std::size_t dest = 0;
if (input[0] != input[1])
++dest;
for (std::size_t source = 1; source < input.size() - 2; source++) {
if (input[source] != input[source-1] && input[source] != input[source+1]) {
input[dest++] = input[source];
}
}
if (input[input.size()-1] != input[input.size()-2]) {
input[dest++] = input[input.size() - 1];
}
input.resize(dest);
}
至少在我看来，这里要记住的重要事情是一般模式。您几乎肯定会遇到更多情况，您希望将一些输入过滤为符合某些条件的输入，而这种跟踪源和目标的基本模式，并仅将那些从源复制到符合您条件的目标有效在很多情况下，不仅仅是这种情况。