第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0047. 全排列 II

题目地址(47. 全排列 II)

题目描述

1
给定一个可包含重复数字的序列,返回所有不重复的全排列。
2
3
示例:
4
5
输入: [1,1,2]
6
输出:
7
[
8
[1,1,2],
9
[1,2,1],
10
[2,1,1]
11
]
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

回溯的基本思路清参考上方的回溯专题。
这道题和第 46 题不一样的点在于其有重复元素。比如题目给的 [1,1,2]。
如果按照 46 题的解法,那么就会有重复的排列。 回顾一下 46 题我们的逻辑。以 [1,1,2] 为例,我们的逻辑是:
  • 先从 [1,1,2] 选取一个数。
  • 然后继续从 [1,1,2] 选取一个数,并且这个数不能是已经选取过的数。
  • 重复这个过程直到选取的数字达到了 3。
如果继续沿用上面的逻辑,那么我们是永远无法拿到全部三个数字的,因此我们的逻辑需要变化。
这里我的算法是记录每一个被选取的索引,而不是值,这就保证了同一个数字不会被选取多次,并且可以选取所有数字了
不过这还是有一个问题。 仍然以 [1,1,2] 为例,如果第一次选取了第一个 1,第二次选取了第二个 1,这就产生了一个组合 [1,1,2]。 如果继续第一次选取了第二个 1,而第二次选取了第一个 1,那么又会产生组合 [1,1,2],可以看出这两个组合是重复的。(题目认为这两种情况应该算一种)
一个解决方案是对 nums 进行一次排序,并规定如果 i > 0 and nums[i] == nums[i - 1] and visited[i - 1], 则不进行选取即可。
经过这样的处理,每次实际上都是从后往前依次重复的数。仍然以上面的 [1,1,2] 为例。[1,1,2] 这个排列一定是先取的第二个 1,再取第一个 1,最后取的 2。这样可以避免重复的原因在于:如果先取的第一个 1,那么永远无法取到三个数,便形成了一个不可行解。

关键点解析

  • 回溯法
  • backtrack 解题公式

代码

  • 语言支持: Javascript,Python3, CPP
JS Code:
1
/*
2
* @lc app=leetcode id=47 lang=javascript
3
*
4
* [47] Permutations II
5
*/
6
function backtrack(list, nums, tempList, visited) {
7
if (tempList.length === nums.length) return list.push([...tempList]);
8
for (let i = 0; i < nums.length; i++) {
9
// 和46.permutations的区别是这道题的nums是可以重复的
10
// 我们需要过滤这种情况
11
if (visited[i]) continue; // 同一个数字不能用两次
12
if (i > 0 && nums[i] === nums[i - 1] && visited[i - 1]) continue; // 同样值的数字不能用两次
13
14
visited[i] = true;
15
tempList.push(nums[i]);
16
backtrack(list, nums, tempList, visited);
17
visited[i] = false;
18
tempList.pop();
19
}
20
}
21
/**
22
* @param {number[]} nums
23
* @return {number[][]}
24
*/
25
var permuteUnique = function (nums) {
26
const list = [];
27
backtrack(
28
list,
29
nums.sort((a, b) => a - b),
30
[],
31
[]
32
);
33
return list;
34
};
Copied!
Python3 code:
1
class Solution:
2
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
3
"""与46题一样,当然也可以直接调用itertools的函数,然后去重"""
4
return list(set(itertools.permutations(nums)))
5
6
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
7
"""自己写回溯法,与46题相比,需要去重"""
8
# 排序是为了方便去重
9
nums.sort()
10
res = []
11
def backtrack(nums, pre_list):
12
if len(nums) <= 0:
13
res.append(pre_list)
14
else:
15
for i in range(len(nums)):
16
# 同样值的数字只能使用一次
17
if i > 0 and nums[i] == nums[i-1]:
18
continue
19
p_list = pre_list.copy()
20
p_list.append(nums[i])
21
left_nums = nums.copy()
22
left_nums.pop(i)
23
backtrack(left_nums, p_list)
24
backtrack(nums, [])
25
return res
Copied!
CPP Code:
1
class Solution {
2
private:
3
vector<vector<int>> ans;
4
void permute(vector<int> nums, int start) {
5
if (start == nums.size() - 1) {
6
ans.push_back(nums);
7
return;
8
}
9
for (int i = start; i < nums.size(); ++i) {
10
if (i != start && nums[i] == nums[start]) continue;
11
swap(nums[i], nums[start]);
12
permute(nums, start + 1);
13
}
14
}
15
public:
16
vector<vector<int>> permuteUnique(vector<int>& nums) {
17
sort(nums.begin(), nums.end());
18
permute(nums, 0);
19
return ans;
20
}
21
};
Copied!

相关题目