LeetCode#46、#47全排列
#46
#47
今天的每日一题是一个全排列的升级版，突然发现忘记了全排列怎么写..（菜）
就顺便做了46题，裸的全排列，记录一下思路。
先看裸的全排列，我们直接想到的就是直接分别以每一个数为第一个数，遍历所有的可能性，但是因为我们不知道数组中有多少个数，所以我们就没法确定要写多少层的循环也不是能写所以这时候我们就需要用到深搜/广搜的想法，通过递归和回溯的方法来进行基本的遍历。
为了避免重复，我们可以写一个标记数组来记录在当前的递归中这个数是否已经使用过，然后再回溯的时候再取消标记，当然对于这种简单的递归我们也可以省去一点空间复杂度，直接当遍历到第pos个数的时候和当前循环中的第i个数进行交换，以达到全排列的效果。其原理是我们可以把从0-pos的数认为是已经选择过的，pos+1-size()-1即为未选择过的
#46代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
void dfs(vector<vector<int> >&ans,vector<int>&nums,int pos)
{
if(pos == nums.size())
{
ans.push_back(nums);
return;
}
for(int i = pos ; i < nums.size() ; i++)
{
swap(nums[i],nums[pos]);
dfs(ans,nums,pos+1);
swap(nums[i],nums[pos]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> >ans;
dfs(ans,nums,0);
return ans;
}
};
|
#47和#46的区别就是给定的数组中可能存在相同的数字，这样就导致我们如果照常进行全排列遍历就有可能出现重复的情况，我用的是一个比较笨的方法，直接使用set容器来进行去重（set毕竟是基于红黑树的操作，速度还是很快（慢）
的，这样的结果就是时间复杂度和空间复杂度都很高，但是方便。还有一种方法，先使用sort对给定的数组进行排序，这样在递归回溯过程中就可以进行判断，配合标记数组，时间复杂度会快很多，但是由于我没写明白所以…建议去看题解(逃)
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
37
38
| class Solution {
public:
void dfs(vector<int>&flag,vector<vector<int> >&ans,vector<int>&nums,vector<int>&temp,int pos)
{
if(pos == nums.size())
{
ans.push_back(temp);
return;
}
for(int i = 0 ; i < nums.size() ; i++)
{
if(!flag[i])
{ flag[i] = 1;
temp.push_back(nums[i]);
dfs(flag,ans,nums,temp,pos+1);
flag[i] = 0;
temp.pop_back();}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int> >ans;
vector<int>flag(nums.size(),0);
vector<int>temp;
dfs(flag,ans,nums,temp,0);
set<vector<int> >s;
set<vector<int> >::iterator it;
vector<vector<int> >ansr;
for(int i = 0 ; i < ans.size() ; i++)
{
s.insert(ans[i]);
}
for(it = s.begin() ; it != s.end() ;it++)
{
ansr.push_back(*it);
}
return ansr;
}
};
|
