从列表中删除重复项
问题描述:
我正在执行着名的“集合子集”问题。我想我有一个很好的工作解决方案,但它包含重复。我希望list.unique()会考虑到这种情况,但是因为对于一个==操作符没有定义,它不起作用。一套集合也不能解决这种情况(现在使用集合列表)。从列表中删除重复项
有80%完整的解决方案,我意识到有一个更好的算法比我来。但我想知道是否有一个聪明的方法来删除重复,而不完全重写算法?
这里是我的代码:
main.cpp中:
#include "random.hpp"
using namespace std;
int main(void) {
subsets2();
getchar();
return 0;
}
Random.Cpp:
void getSubsets2(set<int> myset, list<set<int> > * ptr, int length) {
if (length == 1) {
ptr->push_back(myset);
}
else {
set<int> second(myset);
set<int>::iterator it;
ptr->push_back(myset);
it = myset.begin();
myset.erase(it);
it = second.begin();
++it;
second.erase(it);
getSubsets2(myset, ptr, length - 1);
getSubsets2(second, ptr, length - 1);
}
}
void subsets2(void) {
const int N = 4;
int myints[N] = {
88, 33, 23, 22
};
set<int> myset(myints, myints + N);
set<int> set2;
list<set<int> > mylist;
list<set<int> > * ptr;
ptr = & mylist;
list<set<int> > ::iterator it;
set<int>::iterator it2;
getSubsets2(myset, ptr, N);
mylist.unique();
for (it = mylist.begin(); it != mylist.end(); ++it) {
set2 = * it;
for (it2 = set2.begin(); it2 != set2.end(); ++it2) {
cout << * it2 << " ";
}
cout << "\n";
}
}
输出:
22 23 33 88
23 33 88
33 88
88
33
23 88
88
23
22 33 88
33 88
88
33
22 88
88
22
答
独特的()删除所有consecutive
重复来自c的元素ontainer。因此,在运行unique()之前,需要先对mylist进行排序。
mylist.sort();
mylist.unique();
答
正如另一种方式那样,std::less<T>
是为所有标准容器定义的。因此,我们可以定义如下:
std::set<std::set<int>, std::less<std::set<int>>> set_of_sets;
这会自动筛选出重复集。一个完整的例子:
#include <set>
#include <vector>
#include <iostream>
#include <functional>
int main()
{
std::vector<std::vector<int>> x = {{1,2,3}, {1,2}, {1,2,3}, {4,5,6},
{4,5}, {5,6}, {4,5,6}};
std::set<std::set<int>, std::less<std::set<int>>> set_of_sets;
for(auto it = x.begin(); it != x.end(); ++it) {
std::set<int> s;
s.insert(it->begin(), it->end());
set_of_sets.insert(s);
}
for(auto it = set_of_sets.begin(); it != set_of_sets.end(); ++it) {
std::cout << "{";
for(auto it2 = it->begin(); it2 != it->end(); ++it2) {
std::cout << *it2 << ", ";
}
std::cout << "}\n";
}
return 0;
}
答
使用字符串列表来存储最终结果:
list<string> uniq_list;
for (it = mylist.begin(); it != mylist.end(); ++it) {
set2 = * it;
stringstream ss;
for (it2 = set2.begin(); it2 != set2.end(); ++it2) {
ss << * it2 << " ";
}
uniq_list.push_back(ss.str());
}
uniq_list.sort();
uniq_list.unique();
for (list<string>::iterator it=uniq_list.begin(); it != uniq_list.end(); it++){
cout << *it << endl;
}
还有一个'模板无效独特(BinaryPredicate binary_pred);'对列表定义。当然,唯一性只会删除列表中的“下一个”元素。 – Yuushi
删除重复项目听起来像是一个bandaid以解决更严重的问题。为什么您的代码首先创建重复项?这个问题的一个好的算法应该避免完全重复创建。 –