题目大意
#
描述:给定一个可包含重复数字的序列 nums
。
要求:按任意顺序返回所有不重复的全排列。
说明:
- $1 \le nums.length \le 8$。
- $-10 \le nums[i] \le 10$。
示例:
1
2
|
输入:nums = [1,1,2]
输出:[[1,1,2],[1,2,1],[2,1,1]]
|
1
2
|
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
|
解题思路
#
思路 1:回溯算法
#
这道题跟「
0046. 全排列」不一样的地方在于增加了序列中的元素可重复这一条件。这就涉及到了如何去重。
我们可以先对数组 nums
进行排序,然后使用一个数组 visited
标记该元素在当前排列中是否被访问过。
如果未被访问过则将其加入排列中,并在访问后将该元素变为未访问状态。
然后再递归遍历下一层元素之前,增加一句语句进行判重:if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]: continue
。
然后再进行回溯遍历。
思路 1:代码
#
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
|
class Solution:
res = []
path = []
def backtrack(self, nums: List[int], visited: List[bool]):
if len(self.path) == len(nums):
self.res.append(self.path[:])
return
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
continue
if not visited[i]:
visited[i] = True
self.path.append(nums[i])
self.backtrack(nums, visited)
self.path.pop()
visited[i] = False
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.res.clear()
self.path.clear()
nums.sort()
visited = [False for _ in range(len(nums))]
self.backtrack(nums, visited)
return self.res
|
思路 1:复杂度分析
#
- 时间复杂度:$O(n \times n!)$,其中 $n$ 为数组
nums
的元素个数。
- 空间复杂度:$O(n)$。