文章目录
- 问题描述
- 问题分析
- 问题解法
问题描述
问题链接：https://leetcode.com/problems/permutations/
给定一个不包含重复元素的整数集合，返回全排列的所有结果
leetcode，medium
46：Permutations
Given a collection of distinct integers, return all possible permutations.
问题分析
既然是全排列，首先想到暴力求解法，但是明显不合适，那呆写很多层for循环，无法想象。
对于这种问题，最简便的方法就是递归求解法，因为数组（输入的集合可以以数组形式输入）中的每个元素可以同等对待，而且每个元素都可能处于最终排列的任意位置。因此，瓷器的解法也是递归解法。这里提供两种解法：
解法1思路：从原数组中拿出来一个元素（pop掉），append进全排列数组中，直到原数组的所有元素都被拿出来，则此时全排列数组成为所有输出结果数组中一个。
解法2思路：将原数组的第一个元素拿出来（pop掉），加入到全排列数组中，但是跟思路1不同的是，思路1直接加入到全排列数组的最后，而这里是分别加入到全排列数组的每一个可能的位置，例如全排列数组当前的元素数量是5个，那么有6个位置可以加入新的元素，例如下图中，在1之前、1跟3之间、3跟6之间、6跟2之间、2跟7之间、7之后都可以加入新的元素，因此就有6种结果。
问题解法
解法1代码如下：
复制代码
1
2
3
4
5
6
7
8
9
10
11def permutations(nums): def fun(nums_fun, path, res): if not nums_fun: return res.append(path) for i in range(0, len(nums_fun)): fun(nums_fun[:i] + nums_fun[i+1:], path + [nums_fun[i]], res) res = [] n = len(nums) fun(nums, [], res) return res
解法2代码如下：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12def permutations(nums): def fun1(nums_fun1, insert_res): if len(nums_fun1) == 0: res.append(insert_res) else: for j in range(0, len(insert_res) + 1): fun1(nums_fun1[1:] if len(nums_fun1) > 1 else [], insert_res[:j] + [nums_fun1[0]] + insert_res[j:]) res = [] n = len(nums) fun1(nums, []) return res
测试代码如下：
复制代码
1
2
3
4if __name__ == "__main__": nums = [1, 2, 3] print(permutations(nums))
最后
以上就是潇洒钢笔最近收集整理的关于leetcode-数组的全排列的所有结果 思路与代码的全部内容，更多相关leetcode-数组的全排列的所有结果内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复