leetcode 47 全排列 II 可重复全排列

缘起

继续全排列之旅!!! leetcode 47 全排列 II

分析

1
2
3
4
5
6
7
8
9
10
11
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

和【1】不同，这里数字可能重复. 有dfs和【2】两种做法. dfs的做法借鉴了【3】的做法. 就是区分这些相同的数字. 规定其顺序. 但是太麻烦, 就没实现了

还有一种更自然的做法就是用【2】. 因为【2】都已经搞出下一个了~ 

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		vector<vector<int>> ans;
		sort(nums.begin(), nums.end()); // 先找到最小的
		do 
		{
			ans.push_back(nums);
			vector<int> t = nextPermutation(nums);
			nums = t;
		} while (!inscre(nums));
		return ans;
	}

private:

	bool inscre(vector<int> &nums) // 检查nums是不是非降的
	{
		for (int i =0; i<nums.size()-1; i++)
		{
			if (nums[i]>nums[i+1])
			{
				return false;
			}
		}
		return true;
	}

	vector<int> nextPermutation(vector<int>& nums) {
		int n = nums.size();
		vector<int> kk;
		kk.push_back(nums[n-1]);
		nums.pop_back();
		while(!nums.empty() && nums.back()>=kk.back())
		{
			int t = nums.back();
			nums.pop_back();
			kk.push_back(t);
		}
		if (nums.empty())
		{
			return kk;
		}
		else
		{
			vector<int> ans;
			vector<int>::iterator x = upper_bound(kk.begin(), kk.end(), nums.back());
			swap(nums.back(), *x);
			for (vector<int>::iterator vit = nums.begin(); vit!=nums.end(); vit++)
			{
				ans.push_back(*vit);
			}
			for (vector<int>::iterator vit = kk.begin(); vit!=kk.end(); vit++)
			{
				ans.push_back(*vit);
			}
			return ans;
		}
	}
};

ac情况

1
2
3
4
5
6
7
8
9
执行结果：

通过

显示详情

执行用时 :36 ms, 在所有 C++ 提交中击败了82.48%的用户

内存消耗 :10.7 MB, 在所有 C++ 提交中击败了53.48%的用户

参考

【1】https://yfsyfs.github.io/2019/09/13/leetcode-46-%E5%85%A8%E6%8E%92%E5%88%97-%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/

【2】https://yfsyfs.github.io/2019/09/13/leetcode-31-%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%8E%92%E5%88%97/

【3】https://yfsyfs.github.io/2019/09/06/%E4%B8%80%E8%91%97%E5%90%8D%E8%BD%AF%E4%BB%B6%E5%85%AC%E5%8F%B8%E7%9A%84java%E7%AC%94%E8%AF%95%E7%AE%97%E6%B3%95%E9%A2%98-%E6%95%B0%E5%AD%97%E6%8E%92%E5%BA%8F/