We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
本题和全排列-46 的思路是一样的,只是在每次递归保存的时候,利用 Set 去重的特性,把每个值用字符串拼接的方式丢进 set 里去重,最后再处理成题目需要的格式即可。
Set
let uniqSymbol = 'X' let permuteUnique = function (nums) { let n = nums.length if (n === 1) { return [nums] } let permuteSet = (nums) => { let n = nums.length if (n === 0) { return new Set() } if (n === 1) { return new Set(nums) } let res = new Set() for (let i = 0; i < n; i++) { let use = nums[i] if (use === undefined) { continue } let rest = nums.slice(0, i).concat(nums.slice(i + 1, n)) let restPermuteds = permuteSet(rest) restPermuteds.forEach((restPermuted) => { res.add(`${use}${uniqSymbol}${restPermuted}`) }) } return res } let permuted = permuteSet(nums) return Array.from(permuted).map((val) => val.split(uniqSymbol).map(Number)) }
The text was updated successfully, but these errors were encountered:
和 全排列 思路一样的回溯法,不过要在回溯过程中增加判断去重,一开始要先排好序:
var permuteUnique = function (nums) { const res = []; const len = nums.length; // 先排序,目的是为了把重复的数字放到一起形成连续,便于后面判断 nums.sort((a, b) => a - b); var backtracking = function (used, path) { if (path.length === len) { res.push([...path]); } for (let i = 0; i < len; i++) { if (used[i]) continue; // 现在假如 第二个数字也是 1,和第一个 1 重复了: // 1.首先下标肯定要大于等于 0 // 2.前后数字相等 // 3.前面的数字必须标记为 使用过了 ,如果没有这个判断,后面的逻辑都到不了,仔细想想就知道了。 if (i - 1 >= 0 && nums[i - 1] === nums[i] && !used[i - 1]) continue; path.push(nums[i]); used[i] = true; backtracking(used, path); path.pop(); used[i] = false; } } backtracking([], []); return res; };
Sorry, something went wrong.
No branches or pull requests
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
本题和全排列-46 的思路是一样的,只是在每次递归保存的时候,利用
Set
去重的特性,把每个值用字符串拼接的方式丢进 set 里去重,最后再处理成题目需要的格式即可。The text was updated successfully, but these errors were encountered: