给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路:在全排列I的基础上,加上去重即可
怎么去重:先把数组进行排序,然后在放到临时数组时,如果数组的前一个数和当前数一样且前一个数还没放过,则跳过这个数的放入
效率:30.18%
class Solution {
public:
int nums_size;
vector<vector<int>> res;
vector<int> temp;
vector<bool> is_visit;
void put_in(vector<int>& nums) {
if (temp.size() == nums_size) {
res.push_back(temp);
}
else {
for (int i = 0; i < nums_size; i++) {
if (is_visit[i] == false) {
if (i > 0 && nums[i-1] == nums[i] && is_visit[i-1] == false)
continue;
is_visit[i] = true;
temp.push_back(nums[i]);
put_in(nums);
temp.pop_back();
is_visit[i] = false;
}
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
nums_size = nums.size();
is_visit.resize(nums_size, false);
put_in(nums);
return res;
}
};