如果笔记

如果笔记

做有价值的技术笔记

【算法第2期】无重复数的全排列(LeetCode 46)

本期讲 LeetCode 第 46 题:无重复数的全排列

本期讲 LeetCode 第 46 题:无重复数的全排列。例如: ``` 输入:[1,2,3] 输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 输出结果的顺序可以随意 ``` ### 解法1:简单青年 最简单的思路:依次从数组里选取一个数,然后把剩下的其他数递归调用当前函数,最后把选取的数填进返回结果的每一个排列里,即可得到最终结果。 执行过程: ``` 输入:[1,2,3] 选取 1,把剩下的 [2,3] 递归调用当前过程,会返回:[[2,3], [3,2]] 把 1 填进上面的返回结果,即得到以 1 开头的全部排列:[[1,2,3], [1,3,2]] 接着选取 2,把剩下的 [1,3] 递归调用当前过程,会返回:[[1,3], [3,1]] 把 2 填进上面的返回结果,即得到以 2 开头的全部排列:[[2,1,3], [2,3,1]] 依此过程选取完所有数即得最终结果 ``` 代码: ```javascript function permute_v1(arr) { const n = arr.length if (n < 2) { return n ? [arr] : arr } const result = [] // 依次选取数组里的每个数 for (let i = 0; i < n; i++) { const nextArr = [...arr] nextArr.splice(i, 1) // 把剩下的数递归调用当前函数 permute_v1(nextArr).forEach(perm => { // 把选取的数填进递归结果 result.push([arr[i]].concat(perm)) }) } return result } ``` ### 解法2:普通青年 对解法 1 改进,调用参数增加一个起始位置`start`。 思路跟解法 1 一样,只是把剩下数作为参数的时候,不生成新数组,而是把选取的数与 start 位置的数交换,递归完了再交换回去。以此降低空间复杂度。 代码: ```javascript function permute(arr) { return permute_v2(arr, 0) } function permute_v2(arr, start) { const n = arr.length if (n <= start + 1) { return n ? [arr[start]] : [] } const result = [] for (let i = start; i < n; i++) { // 把 i 位置的数与 start 位置的数交换,避免新创建数组 i > start && swap(arr, i, start) // 递归时,start 加 1,即全排列参数的起始位置往后挪一位 permute_v2(arr, start + 1).forEach(perm => { result.push([arr[start]].concat(perm)) }) i > start && swap(arr, i, start) } return result } function swap(arr, i, j) { const temp = arr[i] arr[i] = arr[j] arr[j] = temp } ``` 上面的代码里,递归调用后,还要遍历一遍结果,这个遍历有点多余,可以优化如下: ```javascript function permute(arr) { const result = [] permute_v2(arr, 0, [], result) return result } function permute_v2(arr, start, carry, result) { const count = arr.length if (count <= start + 1) { count && result.push(carry.concat(arr[start])) return } for (let i = start; i < count; i++) { i > start && swap(arr, i, start) permute_v2(arr, start + 1, carry.concat(arr[start]), result) i > start && swap(arr, i, start) } } ``` ### 解法3:进步青年 > 利用**对称性** 如果全排列结果的顺序不重要,那么输入 [1,2,3] 跟输入 [2,1,3] 得到的排列结果是一样的,即输入参数的顺序跟输出结果无关。我们可以把这种情况称为**输入参数的对称性**。 或者从另外一个角度来看,输入 [1,2,3] 时: ``` 以 1 开头的全排列结果:[[1,2,3], [1,3,2]] 以 2 开头的全排列结果:[[2,1,3], [2,3,1]] 以 3 开头的全排列结果:[[3,1,2], [3,2,1]] ``` 观察以上结果发现,在 1 的结果里,分别把 1 与 2 交换位置,就得到了 2 的结果;分别把 1 与 3 交换位置,就得到了 3 的结果。现在可以理解这种对称性了吧?。。 基于这样的对称性,只要算出以一个数开头的所有排列,那么即可以通过交换位置得到所有结果。 代码: ```javascript function permute_v3(arr) { const n = arr.length if (n < 2) { return n ? [arr.slice()] : [] // arr.slice() 等于浅拷贝数组 arr } else if (n === 2) { return [arr.slice(), [arr[1], arr[0]]] } const result = [] const perm = permute_v3(arr.slice(1)) const pn = perm.length const posMap = Object.create(null) arr.forEach(item => posMap[item] = []) for (let i = 0; i < pn; i++) { perm[i].forEach((item, index) => posMap[item].push(index + 1)) result.push([arr[0]].concat(perm[i])) } for (let j = 1; j < n; j++) { for (let i = 0, row; i < pn; i++) { row = result[i].slice() swap(row, 0, posMap[arr[j]][i]) result.push(row) } } return result } ``` 这种解法明显减少了递归次数,时间比解法 3 大幅减少。限于篇幅,就不解读代码了。(网上一般看不到这种解法) ### 解法4:优秀青年 有没有不用递归的解法?有! 分析过程: ``` 输入 [1,2] 时,选取 1,然后分别在 1 的前和后插入 2,即得到结果:[[1,2](从后面插), [2,1](从前面插)] 输入 [1,2,3] 时,按上面的过程先得到 [1,2] 的结果 [[1,2], [2,1]],然后把 3 分别插到这个结果的每一个位置: 插到第一组 [1,2] 的每一个位置得到:[1,2,3], [1,3,2], [3,1,2](即分别插到后、中、前) 插到第二组 [2,1] 的每一个位置得到:[2,1,3], [2,3,1], [3,2,1](即分别插到后、中、前) ``` 把上述过程写成代码: ```javascript function permute_v4(arr) { const n = arr.length const result = n ? [[arr[0]]] : [] for (let i = 1; i < n; i++) { for (let j = result.length; j--;) { let item = result[j] let k = item.length let newItem while (k--) { newItem = item.slice() newItem.splice(k, 0, arr[i]) result.push(newItem) } item.push(arr[i]) } } return result } ``` ### 性能分析 数组长度为 10 时,解法 3 和解法 4 的时间都明显少于其他解法很多。 看似没有递归的解法 4 会优于解法 3 很多,实际上简单测试发现解法 3 在时间上还略微少于解法 4。但解法 4 的空间复杂度是最低的,最终结果需要多少空间,执行过程中就最多只用了那么多空间。 ### 课后作业 解法 4 其实在本质上也是利用了**对称性**原理,所以把解法 4 的代码稍微改一下就能得到无递归版的解法 3,感兴趣的话自己尝试一下吧。代码在下期放出。 --- 下期预告:有重复数的全排列

前端, 全排列

算法

hahaboy