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

题目地址(46. 全排列)

题目描述

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

前置知识

公司

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

思路

回溯的基本思路清参考上方的回溯专题。
以 [1,2,3] 为例,我们的逻辑是:
  • 先从 [1,2,3] 选取一个数。
  • 然后继续从 [1,2,3] 选取一个数,并且这个数不能是已经选取过的数。
如何确保这个数不能是已经选取过的数?我们可以直接在已经选取的数字中线性查找,也可以将已经选取的数字中放到 hashset 中,这样就可以在 $O(1)$ 的时间来判断是否已经被选取了,只不过需要额外的空间。
  • 重复这个过程直到选取的数字个数达到了 3。

关键点解析

  • 回溯法
  • backtrack 解题公式

代码

  • 语言支持: Javascript, Python3,CPP
Javascript Code:
1
function backtrack(list, tempList, nums) {
2
if (tempList.length === nums.length) return list.push([...tempList]);
3
for (let i = 0; i < nums.length; i++) {
4
if (tempList.includes(nums[i])) continue;
5
tempList.push(nums[i]);
6
backtrack(list, tempList, nums);
7
tempList.pop();
8
}
9
}
10
/**
11
* @param {number[]} nums
12
* @return {number[][]}
13
*/
14
var permute = function (nums) {
15
const list = [];
16
backtrack(list, [], nums);
17
return list;
18
};
Copied!
Python3 Code:
1
class Solution:
2
def permute(self, nums: List[int]) -> List[List[int]]:
3
"""itertools库内置了这个函数"""
4
import itertools
5
return itertools.permutations(nums)
6
7
def permute2(self, nums: List[int]) -> List[List[int]]:
8
"""自己写回溯法"""
9
res = []
10
def backtrack(nums, pre_list):
11
if len(nums) <= 0:
12
res.append(pre_list)
13
else:
14
for i in nums:
15
# 注意copy一份新的调用,否则无法正常循环
16
p_list = pre_list.copy()
17
p_list.append(i)
18
left_nums = nums.copy()
19
left_nums.remove(i)
20
backtrack(left_nums, p_list)
21
backtrack(nums, [])
22
return res
23
24
def permute3(self, nums: List[int]) -> List[List[int]]:
25
"""回溯的另一种写法"""
26
res = []
27
length = len(nums)
28
def backtrack(start=0):
29
if start == length:
30
# nums[:] 返回 nums 的一个副本,指向新的引用,这样后续的操作不会影响已经已知解
31
res.append(nums[:])
32
for i in range(start, length):
33
nums[start], nums[i] = nums[i], nums[start]
34
backtrack(start+1)
35
nums[start], nums[i] = nums[i], nums[start]
36
backtrack()
37
return res
Copied!
CPP Code:
1
class Solution {
2
vector<vector<int>> ans;
3
void dfs(vector<int> &nums, int start) {
4
if (start == nums.size() - 1) {
5
ans.push_back(nums);
6
return;
7
}
8
for (int i = start; i < nums.size(); ++i) {
9
swap(nums[i], nums[start]);
10
dfs(nums, start + 1);
11
swap(nums[i], nums[start]);
12
}
13
}
14
public:
15
vector<vector<int>> permute(vector<int>& nums) {
16
dfs(nums, 0);
17
return ans;
18
}
19
};
Copied!
复杂度分析 令 N 为数组长度。
  • 时间复杂度:$O(N!)$
  • 空间复杂度:$O(N)$

相关题目