如果笔记

如果笔记

做有价值的技术笔记

【算法第3期】有重复数的全排列(LeetCode 47)

本期讲述 LeetCode 47,有重复数的全排列

[上期](https://ifnote.cn/note/143) 留了一个课后作业,我们先来看下答案。因为第 47 题跟第 46 题是关联的,实际上用 46 题的解法加个条件判断就是 47 题的解法,所以我们先来回顾下 46 题。 第 46 题解法四: ```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 } ``` 上期里说了这本质上也是利用了**输入参数的对称性**,为什么这么说呢? 把解法四的代码稍微改下即实现无递归版的解法三: ```javascript function permute(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, last = k let newItem item.push(arr[i]) // push 之后,last 即指向 arr[i] (item 最后一个元素) while (k--) { newItem = item.slice() // 每次复制当前排列 // 交换 last 所指的元素和 k 所指的元素,newItem 即变成一个新的排列 swap(newItem, k, last) result.push(newItem) } } } return result } ``` 对比这两段代码,一个是把 arr[i] 从后到前依次插入每一个位置,每插入一次便形成一个新的排列;一个是从后向前依次跟每个元素交换位置,每交换一次便形成一个新的排列。本质上没区别。 ### 有重复数的全排列 LeetCode 第 47 题: ``` 输入:[1,1,2] 输出:[ [1,1,2], [1,2,1], [2,1,1] ] 输出结果的顺序可以随意 ``` 同样,输入数组的元素顺序并不影响最终的排列结果,所以还是可以利用对称性解决。 直接看代码吧,把上面的解法三改下`while`条件改下即可: ```javascript function permute(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, last = k let newItem item.push(arr[i]) // push 之后,last 即指向 arr[i] (item 最后一个元素) // 如果第 k 个元素与 arr[i] 相同,退出循环 // 因为第 k 个元素已经与它前面的元素交换过位置产生过排列,继续循环将产生重复排列 while (k-- && item[k] !== arr[i]) { newItem = item.slice() // 每次复制当前排列 // 交换 last 所指的元素和 k 所指的元素,newItem 即变成一个新的排列 swap(newItem, k, last) result.push(newItem) } } } return result } ``` 不用递归,所用空间也达到最少,这可能是最优解了吧。其他解法就不写了,感兴趣的欢迎评论探讨。 --- 下期预告:大整数的乘法(LeetCode 43)

算法

hahaboy