每日算法:全排列问题
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
- 输入: [1,2,3]
- 输出:
- [
- [1,2,3],
- [1,3,2],
- [2,1,3],
- [2,3,1],
- [3,1,2],
- [3,2,1]
- ]
本题是回溯算法的经典应用场景
1. 算法策略
回溯算法是一种搜索法,试探法,它会在每一步做出选择,一旦发现这个选择无法得到期望结果,就回溯回去,重新做出选择。深度优先搜索利用的就是回溯算法思想。
2. 适用场景
回溯算法很简单,它就是不断的尝试,直到拿到解。它的这种算法思想,使它通常用于解决广度的搜索问题,即从一组可能的解中,选择一个满足要求的解。
3. 代码实现
我们可以写一下,数组 [1, 2, 3] 的全排列有:
先写以 1 开头的全排列,它们是:[1, 2, 3], [1, 3, 2],即 1 + [2, 3] 的全排列;
再写以 2 开头的全排列,它们是:[2, 1, 3], [2, 3, 1],即 2 + [1, 3] 的全排列;
最后写以 3 开头的全排列,它们是:[3, 1, 2], [3, 2, 1],即 3 + [1, 2] 的全排列。
即回溯的处理思想,有点类似枚举搜索。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。
这显然是一个 递归 结构;
- 递归的终止条件是:一个排列中的数字已经选够了 ,因此我们需要一个变量来表示当前程序递归到第几层,我们把这个变量叫做 depth ,或者命名为 index ,表示当前要确定的是某个全排列中下标为 index 的那个数是多少;
- used(object):用于把表示一个数是否被选中,如果这个数字(num)被选择这设置为 used[num] = true ,这样在考虑下一个位置的时候,就能够以 O(1)的时间复杂度判断这个数是否被选择过,这是一种「以空间换时间」的思想。
- let permute = function(nums) {
- // 使用一个数组保存所有可能的全排列
- let res = []
- if (nums.length === 0) {
- return res
- }
- let used = {}, path = []
- dfs(nums, nums.length, 0, path, used, res)
- return res
- }
- let dfs = function(nums, len, depth, path, used, res) {
- // 所有数都填完了
- if (depth === len) {
- res.push([...path])
- return
- }
- for (let i = 0; i < len; i++) {
- if (!used[i]) {
- // 动态维护数组
- path.push(nums[i])
- used[i] = true
- // 继续递归填下一个数
- dfs(nums, len, depth + 1, path, used, res)
- // 撤销操作
- used[i] = false
- path.pop()
- }
- }
- }
4. 复杂度分析
时间复杂度:O(n?n!),其中 n 为序列的长度
这是一个排列组合,每层的排列组合数为:Amn=n!/(n?m)! ,故而所有的排列有 :
A1n + A2n + … + An-1n = n!/(n?1)! + n!/(n?2)! + … + n! = n! * (1/(n?1)! + 1/(n?2)! + … + 1) <= n! * (1 + 1/2 + 1/4 + … + 1/2n-1) < 2 * n!
并且每个内部结点循环 n 次,故非叶子结点的时间复杂度为 O(n?n!)
- 空间复杂度:O(n)
leetcode:https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-wen-ti-by-user7746o/
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击