专业做公司网站的机构,买一个商标大概要多少钱,外贸大型门户网站建设,深圳做网站 汉狮网络LeetCode-47 全排列Ⅱ 题目描述解题思路代码说明 题目描述
给定一个可包含重复数字的序列 nums #xff0c;按任意顺序 返回所有不重复的全排列。
示例 #xff1a;
输入#xff1a;nums [1,1,2]输出#xff1a; [[1,1,2], [1,2,1], [2,1,1]] b站题目解读讲的不好… LeetCode-47 全排列Ⅱ 题目描述解题思路代码说明 题目描述
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
示例
输入nums [1,1,2]输出 [[1,1,2], [1,2,1], [2,1,1]] b站题目解读讲的不好勿喷
解题思路
首先选择对原数组排序保证相同的数字都相邻然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」即如下的判断条件
if (i 0 nums[i] nums[i - 1] used[i-1] false) {continue;
}即可实现树层的去重。 希望在计算的过程中进行去重操作所以我们对数组nums排序处理。 如果nums[i] nums[i-1]就说明该分支有可能是重复的。 但是这个相等条件有两种可能:
一种是1 1‘ 2也就是选择完1之后再选择第二个1两个元素虽然重复但是第二个元素是前一个元素的下一层这时是没有问题的。另一种是之前的 同层 分支已经有 1 1‘ 2了这次的选择是 1‘ 1 2 。两个元素重复且重的是同层路径。那就说明是重复分支。
具体区分的办法是 nums[i-1] 的used状态是被选择的那么说明当前的nums[i] 是 nums[i-1]的下一层路径。 否则如果 nums[i-1] 的状态是没被选择的那么说明当前 的nums[i] 是nums[i-1] 同层路径。
代码
class Solution {
public:
// [] 中的数字可以重复结果集的vector元素不能重复vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());vectorbool used(nums.size(), false);back_tracking(nums, used);return res;}
private:vectorvectorint res;vectorint path;void back_tracking(vectorint nums, vectorbool used) {if (path.size() nums.size()) {res.push_back(path);return;} else {for (int i 0; i nums.size(); i) {if (i 0 nums[i] nums[i-1] used[i-1] false) continue;if (used[i] false) {used[i] true;path.push_back(nums[i]);back_tracking(nums, used);path.pop_back();used[i] false;}}}}
};说明
去重最关键的代码就是
if (i 0 nums[i] nums[i - 1] used[i - 1] false) {continue;
}而改成used[i-1]true也正确
if (i 0 nums[i] nums[i - 1] used[i - 1] true) {continue;
}树层上去重(used[i - 1] false)的树形结构如下 树枝上去重used[i - 1] true的树型结构如下
