题目
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解答
C语言的实现以前总结过,请见 http://www.cnblogs.com/YuNanlong/p/6171459.html
这道题做的我很气,自己写交换vector元素的过程,只击败了30+%的提交,用了swap()函数击败了70+%的。。。
下面是AC的代码:
class Solution {
public:
vector<vector<int>> ans;
vector<int> res;
void permute(vector<int> nums){
int length = nums.size();
if(length == 1){
res.push_back(nums[0]);
ans.push_back(vector<int>(res.begin(), res.end()));
res.pop_back();
return ;
}
else{
int last;
for(int i = 0; i < length; i++){
if(i == 0){
last = nums[i];
}
else if(last == nums[i]){
continue;
}
last = nums[i];
swap(nums[0], nums[i]);
res.push_back(last);
permute(vector<int>(nums.begin() + 1, nums.end()));
res.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
permute(vector<int>(nums.begin(), nums.end()));
return ans;
}
};
107