大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
当有反复元素的时候呢？
不用拍脑袋都会想到一种方法，也是全部有反复元素时的通用处理方法，维护一个set，假设这个元素没增加过就增加，增加过了的忽略掉。可是，在这道题上这个通用方法竟然超时了！
怎么办？想一下为什么会这样，如果我们要排列的数字是1111112，当当前的排列中没有1时，取哪个1生成一遍，都是一样的。仅仅有当前面的1都用过了，必须轮到这个1出场的时候，它才会有价值。更明白一点说，如果我们要在生成的排列中放两个1，那么这两个1是原来的哪两个根本无所谓，不断的选，终于的结果肯定一样，可是当我们要在排列中放3个1的时候，再选择的1一定是新的了，是有意义的。
用算法的语言描写叙述就是，先把全部的候选数字排一下序，同样的数字会挨在一起，对于同样的数字，都先取第一个增加排列，后面的同样的数字想增加排列，必须保证它前面的同样数字已经在排列中了，这样避免了不断生成反复的排列。
class Solution {
public:
set<vector<int> > vis;
void getPerm(vector<int> &num, vector<int> &tpres, vector<vector<int> > &res, int len, int n, bool *visited){
if(len == n){
if(vis.find(tpres) == vis.end()){
vis.insert(tpres);
res.push_back(tpres);
}
return;
}
for(int i=0;i<n;i++){
if(!visited[i]){
if(i!=0&&num[i] == num[i-1]&&!visited[i-1])
continue;
visited[i] = 1;
tpres.push_back(num[i]);
getPerm(num, tpres, res, len+1, n, visited);
visited[i] = 0;
tpres.pop_back();
}
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
vector<int> tpres;
int msize = num.size();
if(msize<=0) return res;
bool visited[msize];
memset(visited, 0, sizeof(visited));
sort(num.begin(), num.end());
getPerm(num, tpres, res, 0, msize, visited);
return res;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118003.html原文链接：https://javaforall.net
