题目描述
给定一个没有重复数字的序列，返回其所有可能的全排列。
题解
还是要回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
int vsize = nums.size();
if (!vsize)return {};
if (vsize == 1)return { nums };
for (int i=0;i<vsize;i++)
{
int t = nums[i];
nums.erase(nums.begin() + i);
for (auto it : permute(nums))
{
it.push_back(t);
res.push_back(it);
}
nums.insert(nums.begin() + i, t);
}
return res;
}
|
言简意赅我觉得不错。就是效率不咋地。
题目描述
给定一个可包含重复数字的序列，返回所有不重复的全排列。
题解
用set去重似乎有点傻。另外nums是无序的，得先排个序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
int vsize = nums.size();
if (vsize <= 1)return { nums };
if (vsize == 2 && nums[0] == nums[1])return { nums };
for (int i=0;i<vsize;i++)
{
int t = nums[i];
if (i < vsize - 1 && nums[i + 1] == t)
continue;
nums.erase(nums.begin() + i);
for (auto it : permute(nums))
{
it.push_back(t);
res.push_back(it);
}
nums.insert(nums.begin() + i, t);
}
return res;
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
return permute(nums);
}
|
啊啊啊啊啊我能说什么！虽然效率不是那么高，但是居然第一次！这么快！一次过！啊哈哈哈哈！！
主要的思路还是基于上一题的回溯，只不过这一题有重复数字，对于重复的数字，在排列时只要跳过他们就好啦，因为划去其中一个，然后进行排列，再把这个数字加进去，这个过程相同的数字之间只需要进行一次就好啦。还需要处理的一个地方是，当nums中只有两个相同元素时，就不用再进行排列，直接返回nums。
如果不改变思路的话，这个效率恐怕是提不上去的，递归用的空间略多。