LeetCode 刷题【47. 全排列 II】

47. 全排列 II

自己做

解1：检查重复

class Solution {
public:void circle(vector<int> nums, vector<vector<int>> &res,int start){int len = nums.size();if(start == len - 1){                       //到头了//检查重复bool is_exist = false;for(int i = 0; i < res.size(); i++){bool same = true;                   //标记是否相同for(int j = 0; j < res[0].size(); j++)if(nums[j] != res[i][j]){          //不相同same = false;break;}if(same){                           //出现了相同is_exist = true;                //标记重复break;}}if(!is_exist)res.push_back(nums);                    //加入结果中return;}for(int i = start; i < len; i++){if(i == start || nums[i] != nums[start]){swap(nums[i], nums[start]);             //交换circle(nums, res, start + 1);           //进入下一层循环swap(nums[i], nums[start]);             //归位}}}vector<vector<int>> permuteUnique(vector<int>& nums) {int len = nums.size();vector<vector<int>> res;circle(nums, res, 0);return res;}
};

看题解

官方代码：

首先通过排序将重复元素全部堆一起

判断条件中

vis[i] 表示该元素是否被取过

i > 0 && nums[i] == nums[i - 1] && !vis[i - 1] 表示该元素是否与上个元素相同，如果相同并且上个元素没取过则取该元素

class Solution {vector<int> vis;public:void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {if (idx == nums.size()) {ans.emplace_back(perm);return;}for (int i = 0; i < (int)nums.size(); ++i) {if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}perm.emplace_back(nums[i]);vis[i] = 1;backtrack(nums, ans, idx + 1, perm);vis[i] = 0;perm.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> ans;vector<int> perm;vis.resize(nums.size());sort(nums.begin(), nums.end());backtrack(nums, ans, 0, perm);return ans;}
};