leetcode46、47、31 全排列、下一个排列（非递归解法，减少空间复杂度）

31. 下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。

解法：
需要找到第一个比该排列大的排列，那么首先就要找到原序列中相邻两个数左侧小于右侧的数，如 [1,3,2] 中的1，下标记为i
此时需要找到从右开始第一个大于ai的数下标j，此时需要将i，j数字互换，因为我们要找到的是第一个大于该排列的数，互换后此时并不是第一个大于，需要保证i后面的最小，因此把i后面的排列反转。
很容易看出来[1,3,2]中ai为1,aj为2,交换后[2,3,1]，此时并不是最小需要反转[1,3]

void nextPermutation(vector<int> &nums)
{
    int i=nums.size()-2;
    while(i>=0&&nums[i]>=nums[i+1]) i--;
    if(i>=0)
    {
        int j=nums.size()-1;
        while (nums[j]<=nums[i]) j--;
        swap(nums[i],nums[j]);
        
    }
    reverse(nums.begin()+i+1,nums.end());

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解法一：
最基础的解法使用回溯法，n个位置使用深度优先搜索枚举每一个位置上的数，使用vis标记之前已经使用过的数，防止重复使用。

void dfs(vector<vector<int>> &ans,vector<int> &path,unordered_map<int,int> &vis,vector<int> nums)
{
	if(path.size()==nums.size())
	{
		ans.push_back(path);
		return;
	}
	for(int x:nums)
	{
		if(vis[x]) continue;
		vis[x]=1;
		path.push_back(x);
		dfs(ans,path,vis,nums);
		vis[x]=0;
		path.pop_back();
	}
}

vector<vector<int>> permute ( vector<int>& nums )
{
	vector<vector<int>> ans;
	vector<int> path;
	unordered_map<int,int> vis;
	for(int i:nums)
	{
		vis[i]=1;
		path.push_back(i);
		dfs(ans,path,vis,nums);
		vis[i]=0;
		path.clear();
	}
	return ans;
}

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

解法二：
解法一中使用了额外的数组vis和path来记录搜索解，可以维护原来的数组，用下标index记录当前需要填写数字的位置，index左侧都是填写好了的数字，右边即为待填写的数字。每次选择右边待填写的数字和要填写的数字进行交换操作。这样可以减少空间复杂度

void dfs(vector<vector<int>> &ans,int index,vector<int> nums)
{
	if(index==nums.size())
	{
		ans.push_back(nums);
		return;
	}
	for(int i=index;i<nums.size();i++)
	{
		swap(nums[index],nums[i]);
		dfs(ans,index+1,nums);
		swap(nums[index],nums[i]);

	}
}
vector<vector<int>> permute ( vector<int>& nums )
{
	vector<vector<int>> ans;
	dfs(ans,0,nums);
	return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

解法三：

上述解法仍使用递归法，会产生额外的递归栈的空间使用情况，如何把该问题转换为迭代解法。即可减少空间复杂度。

非递归解法一：

当 n=1 时，数组中只有一个数 a1，其全排列只有一种，即为 a1
当 n=2 时，数组中此时有 a1a2，其全排列有两种，a1a2 和 a2a1，那么此时考虑和上面那种情况的关系，可以发现，其实就是在 a1 的前后两个位置分别加入了 a2
当 n=3 时，数组中有 a1a2a3，此时全排列有六种，分别为 a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根据上面的结论，实际上是在 a1a2 和 a2a1 的基础上在不同的位置上加入 a3 而得到的。
_ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3
_ a2 _ a1 _ : a3a2a1, a2a3a1, a2a1a3

class Solution {
public:
vector<vector<int>> permute(vector<int>& num) {
        vector<vector<int>> res{{}};
	for(int a:num)
	{
		for(int k=res.size();k;k--) //这里需要用倒序，因为res在下面中在增加新的答案，否则不能跳出循环
		{
			vector<int> t=res.front();
			res.erase(res.begin());//这里需要之前的都清除掉
			for(int i=0;i<=t.size();i++)
			{
				vector<int> ans=t;
				ans.insert(ans.begin()+i,a);
				res.push_back(ans);
			}
		}
	}
        return res;
    }


};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

知乎原文

非递归解法二：
此时就可以使用31题中下一个排列的方法，首先对整个数组进行排序，不断寻找下一个排列，直到找不到下一个排列，即不存在左侧数字小于右侧数字

vector<vector<int>> permuteUnique(vector<int> &nums)
{
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    res.push_back(nums);
    while (true)
    {
        int i = nums.size() - 2;
        int j = nums.size() - 1;
        while (i >= 0 && nums[i] >= nums[i + 1])
            i--;
        if (i >= 0)
        {
            while (nums[j] <= nums[i])
                j--;
            swap(nums[i], nums[j]);
        }
        else break;
        reverse(nums.begin() + i + 1, nums.end());
        res.push_back(nums);
        
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

与上题不同是加了数字可重复条件

解法一
回溯法，仍然使用上述回溯法，那么需要解决的是如何使得重复的数字不会重复得填在该位置上。

此时先对整个数组进行排序，完成排序后，相同的数字就相邻了，可以这样思考，相同的数字中也存在先后顺序，比如1，2，2中，我们设定先填了左边的2，才能填写右边的2，这样就不会出现重复填写。如
1，2a，2b
2a，1，2b
2a，2b，1
如果2a,2b随意顺序就会出现问题
那么只需要判断

if(vis[i]||(i&&nums[i-1]==nums[i]&&!vis[i-1])) continue;
1

即访问过该数或者该数和前一位数相同，但是前一位数未访问，跳过。这样就不会出现重复情况

void dfs(vector<vector<int>>& ans,vector<int>& path,unordered_map<int,int>& vis,vector<int>& nums)
{
	if(path.size()==nums.size())
	{
		ans.push_back(path);
		return;
	}
	for(int i=0;i<nums.size();i++)
	{
		if(vis[i]||(i&&nums[i-1]==nums[i]&&!vis[i-1])) continue;
		vis[i]=1;
		path.push_back(nums[i]);
		dfs(ans,path,vis,nums);
		path.pop_back();
		vis[i]=0;
	}
}
vector<vector<int>> permuteUnique ( vector<int>& nums )
{
    sort(nums.begin(),nums.end());
	vector<vector<int>> ans;
	vector<int> path;
	unordered_map<int,int> vis;
	dfs(ans,path,vis,nums);
	return ans;
}
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>> permuteUnique(vector<int> &nums)
{
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    res.push_back(nums);
    while (true)
    {
        int i = nums.size() - 2;
        int j = nums.size() - 1;
        while (i >= 0 && nums[i] >= nums[i + 1])
            i--;
        if (i >= 0)
        {
            while (nums[j] <= nums[i])
                j--;
            swap(nums[i], nums[j]);
        }
        else break;
        reverse(nums.begin() + i + 1, nums.end());
        res.push_back(nums);
        
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24