题目链接:Permutations II
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], and [2,1,1].
这道题的要求是给定一组数字,包含重复元素,生成所有的排列组合。
这道题是Permutations的基础上,允许数组中有重复元素。不过思路还是类似,只不过需要跳过重复元素。
-
递归排列
这是一个排列的问题,首先联想到的就是递归方式。对剩余元素排序,然后每次逐个固定每个没有重复元素到第一位置,然后递归排列剩下的元素。当固定到前面的元素数量等于数组长度的时候,递归终止。
注意一点,由于排序会造成num数组元素的顺序变化,因此调用两次swap(num[i], num[j])并不能恢复到原样,因此需要去掉递归函数参数num前面的引用符合‘&’,这样每次退出内层函数后,num数组的元素顺序回复原样。不过这样空间复杂度变高,时间复杂度变高了。。。
时间复杂度:O(n!)(结果数量)
空间复杂度:O(n!)
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
27
28
29
30
class Solution
{
public:
vector<vector<int> > permuteUnique(vector<int> &num)
{
vector<vector<int> > vvi;
permuteUnique(num, 0, vvi);
return vvi;
}
private:
void permuteUnique(vector<int> num, int i, vector<vector<int> > &vvi)
{
if(i == num.size())
{
vvi.push_back(num);
return;
}
sort(num.begin() + i, num.end());
for(int j = i; j < num.size(); )
{
swap(num[i], num[j]);
permuteUnique(num, i + 1, vvi);
swap(num[i], num[j]);
while(++ j < num.size() && num[j] == num[j - 1]);
}
}
};
-
next_permutation
由于next_permutation()函数在生成下一排列时候,会跳过重复情形,因此这道题和Permutations完全一样,利用next_permutation()函数,逐步生成下一个排列。由于next_permutation()在最后一个排列时返回false,因此可以先对数组排序,然后调用next_permutation()直到其返回false。
时间复杂度:O(n!)(结果数量)
空间复杂度:O(n!)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution
{
public:
vector<vector<int> > permute(vector<int> &num)
{
sort(num.begin(), num.end());
vector<vector<int> > vvi({num});
while(next_permutation(num.begin(), num.end()))
vvi.push_back(num);
return vvi;
}
};