Given a collection of numbers, return all possible permutations.
For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
求数组元素的全排列,数组不含重复元素
算法1:递归
类似于DFS的递归. 对于包含n个元素的数组,先确定第一位置的元素，第一个位置有n中可能(每次把后面的元素和第一个元素交换)，然后求子数组[2…n]的全排列。由于一个数列的总共有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
|
class
Solution {
public
:
vector<vector<
int
> > permute(vector<
int
> &num) {
vector<vector<
int
> > res;
if
(num.size() == 0)
return
res;
vector<
int
> tmpres;
permuteRecur(num, 0, res, tmpres);
return
res;
}
void
permuteRecur(vector<
int
> &num,
int
index, vector<vector<
int
> >&res, vector<
int
>&tmpres)
{
if
(index == num.size())
{
res.push_back(tmpres);
return
;
}
for
(
int
i = index; i < num.size(); i++)
{
swap(num[index], num[i]);
tmpres.push_back(num[index]);
permuteRecur(num, index+1, res, tmpres);
tmpres.pop_back();
swap(num[index], num[i]);
}
}
};
|
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].
求数组元素的全排列,数组含重复元素
分析：要避免重复，就要保证我们枚举某个位置的元素时，不能枚举重复。
算法2：
在算法1的基础上，当我们枚举第i个位置的元素时，若要把后面第j个元素和i交换，则先要保证[i…j-1]范围内没有和位置j相同的元素。有以下两种做法（1）可以每次在需要交换时进行顺序查找；（2）用哈希表来查重。具体见下面的代码。
注意不要误以为以下两种做法能够去重：（1）最开始先对数组进行排序，以后每次交换时，只要保证当前要交换的元素和前一个元素不同，这种做法是错误的，虽然开始进行了排序，但是元素的交换会使数组再次变的无序（2）每次进入递归函数permuteRecur时，对从当前索引开始的子数组排序，这种做法也是错误的，因为每次交换元素后，我们要恢复交换的元素，如果在递归函数内排序，就不能正确的恢复交换的元素。 本文地址
|
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
31
32
33
34
35
36
|
class
Solution {
public
:
vector<vector<
int
> > permuteUnique(vector<
int
> &num) {
vector<vector<
int
> > res;
if
(num.size() == 0)
return
res;
vector<
int
> tmpres;
permuteRecur(num, 0, res, tmpres);
return
res;
}
void
permuteRecur(vector<
int
> &num,
int
index, vector<vector<
int
> >&res, vector<
int
>&tmpres)
{
if
(index == num.size())
{
res.push_back(tmpres);
return
;
}
for
(
int
i = index; i < num.size(); i++)
if
(i == index || !find(num, index, i, num[i]))
{
swap(num[index], num[i]);
tmpres.push_back(num[index]);
permuteRecur(num, index+1, res, tmpres);
tmpres.pop_back();
swap(num[index], num[i]);
}
}
//从数组的[start,end）范围内寻找元素target
bool
find(vector<
int
> &num,
int
start,
int
end,
int
target)
{
for
(
int
i = start; i < end; i++)
if
(num[i] == target)
return
true
;
return
false
;
}
};
|
|
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
> > res;
if
(num.size() == 0)
return
res;
vector<
int
> tmpres;
permuteRecur(num, 0, res, tmpres);
return
res;
}
void
permuteRecur(vector<
int
> &num,
int
index, vector<vector<
int
> >&res, vector<
int
>&tmpres)
{
if
(index == num.size())
{
res.push_back(tmpres);
return
;
}
unordered_set<
int
> umap;
for
(
int
i = index; i < num.size(); i++)
if
(umap.find(num[i]) == umap.end())
{
umap.insert(num[i]);
swap(num[index], num[i]);
tmpres.push_back(num[index]);
permuteRecur(num, index+1, res, tmpres);
tmpres.pop_back();
swap(num[index], num[i]);
}
}
};
|
算法3：
我们知道c++STL中有个函数next_permutation,这个函数时求某个排列的下一个大的排列。所谓的下一个大的排列可以如下解释：如果把数组元素看成是某个字符，这些字符组成一个字符串，下一个大的排列就是比当前排列代表的字符串更大（按字典序比较），且不存在介于两个字符串之间的字符串。例如对于字符串abc，它的下一个大排列是acb。
对于某个排列，我们如下求它的下一个大的排列：
- 从最尾端开始往前寻找两个相邻的元素，两者满足i < ii（令第一个元素为i，第二个元素为ii）
- 如果没有找到这样的一对元素则，表明当前的排列是最大的，没有下一个大的排列
- 如果找到，再从末尾开始找出第一个大于i的元素，记为j
- 交换元素i, j，再将ii后面的所有元素颠倒排列(包括ii)
- 按照的STL实现，如果某个排列没有比他大的下一个排列，调用这个函数还是会把原排列翻转，即得到最小的排列
有了这个函数后，这一题，我们先对数组按照升序排序，这样初始排列就是最小的，然后循环对数组求next_permutation，直到找不到下一个大的排列。
|
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
> > res;
if
(num.size() == 0)
return
res;
sort(num.begin(), num.end());
res.push_back(num);
while
(mynext_permutation(num))res.push_back(num);
return
res;
}
bool
mynext_permutation(vector<
int
>&num)
{
int
n = num.size();
if
(n <= 1)
return
false
;
for
(
int
i = n-2, ii = n-1; i >= 0; i--,ii--)
{
if
(num[i] < num[ii])
{
int
j = n-1;
while
(num[j] <= num[i])j--;
//从尾部找到第一个比num[i]大的数，一定可以找到
swap(num[i], num[j]);
reverse(num.begin()+ii, num.end());
return
true
;
}
}
reverse(num.begin(), num.end());
return
false
;
}
};
|
STL还有一个prev_permutation函数，求某个排列的上一个比他小的排列，方法和next_permutation相似：
对于某个排列，我们如下求它的上一个更小的排列：
- 从最尾端开始往前寻找两个相邻的元素，两者满足i > ii（令第一个元素为i，第二个元素为ii）
- 如果没有找到这样的一对元素则，表明当前的排列是最小的，没有下一个更小的排列
- 如果找到，再从末尾开始找出第一个小于i的元素，记为j
- 交换元素i, j，再将ii后面的所有元素颠倒排列（包括ii）
- 按照的STL实现，如果某个排列没有比他小的下一个排列，调用这个函数还是会把原排列翻转，即得到最大的排列
有了这个函数后，这一题，我们先对数组按照降序排序，这样初始排列就是最大的，然后循环对数组求prev_permutation，直到找不到下一个更小的排列。
|
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
> > res;
if
(num.size() == 0)
return
res;
sort(num.begin(), num.end(), greater<
int
>());
res.push_back(num);
while
(myprev_permutation(num))res.push_back(num);
return
res;
}
bool
myprev_permutation(vector<
int
>&num)
{
int
n = num.size();
if
(n <= 1)
return
false
;
for
(
int
i = n-2, ii = n-1; i >= 0; i--,ii--)
{
if
(num[i] > num[ii])
{
int
j = n-1;
while
(num[j] >= num[i])j--;
//从尾部找到第一个比num[i]小的数，一定可以找到
swap(num[i], num[j]);
reverse(num.begin()+ii, num.end());
return
true
;
}
}
reverse(num.begin(), num.end());
return
false
;
}
};
|
