阅读量:0
题目
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
解法
分享一下复杂的解法
思路：全排列可以看做在确定的列表上加一个数字，比如[1,2,3]可以看做在[1,2]中加入3，而[1,2]可以看做[1]中加入2。因此，可以定义一个函数，这个函数的作用是每次在自身列表中加入一个数字并且它会调用自己，就能得到一个不停给自己加入数字的列表。
def pailie(self, nums, stack): # print(stack) if len(stack) == len(nums): self.res.append([nums[x] for x in stack]) return i = stack[-1] while i < len(nums)-1: stack.append(i+1) self.pailie(nums, stack) stack.pop() i += 1# 伪代码 for i in range(nums): self.pailie(nums, [i])用列表操作来模拟栈的进出, 注意：栈里边存的是元素下标。上述代码步骤拆分后是这样的，每行代表一次pailie函数执行完毕，为了清楚一点就直接写值了，实际上stack里边存的是下标：
[1] -> [1,2] -> [1,2,3]
[1] -> [1,3]
[2] -> [2,3]
[3]
排列在往列表中加入数字时不仅要考虑后边的元素，也要考虑前边的元素，同时不能选择重复的元素，因此要创建status列表记录每个元素是否被使用
def pailie(self, nums, stack, status): # print(stack) if len(stack) == len(nums): self.res.append([nums[x] for x in stack]) return i = stack[-1] while i < len(nums)-1: if status[i+1] == 0: status[i+1] = 1 stack.append(i+1) self.pailie(nums, stack, status) status[i+1] = 0 stack.pop() i += 1 i = stack[-1] while i > 0 : if status[i-1] == 0: status[i-1] = 1 stack.append(i-1) self.pailie(nums, stack, status) status[i-1] = 0 stack.pop() i -= 1# 伪代码 status = [0] * len(nums) for i in range(len(nums)): status[i] = 1 self.pailie(nums, [i], status) status[i] = 0 return self.res上述代码步骤拆分后是这样的：
[1] -> [1,2] -> [1,2,3]
[1] -> [1,3] -> [1,3,2]
[2] -> [2,3] -> [2,3,1]
[2] -> [2,1] -> [2,1,3]
[3] -> [3,2] -> [3,2,1]
[3] -> [3,1] -> [3,1,2]
总结
时间复杂度应该是O(n^n)， 不适合元素很大的情况。
官方的解法还是比较好的。
