首页 > 代码库 > 【LeetCode】047. Permutations II
【LeetCode】047. Permutations II
题目:
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2]
have the following unique permutations:
[ [1,1,2], [1,2,1], [2,1,1] ]
题解:
Solution 1 (TLE)
class Solution { public: void dfs(vector<int> nums, vector<vector<int>>& vv, vector<int>& v, vector<int>& visited, int level) { if(level >= nums.size()) { if(find(vv.begin(), vv.end(), v) == vv.end()) vv.push_back(v); return; } for(int i=0; i<nums.size(); ++i) { if(visited[i] != 0) continue; v.push_back(nums[i]); visited[i] = 1; dfs(nums, vv, v, visited, level+1); v.pop_back(); visited[i] = 0; } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> vv; vector<int> v, visited(nums.size(),0); dfs(nums, vv, v, visited, 0); return vv; } };
Solution 2 ()
class Solution { public: void dfs(vector<int> nums, vector<vector<int>>& vv, vector<int>& v, vector<int>& visited, int level) { if(level >= nums.size()) { vv.push_back(v); return; } for(int i=0; i<nums.size(); ++i) { if(visited[i] != 0) continue; if(i>0 && nums[i] == nums[i-1] && visited[i-1] == 0) continue; v.push_back(nums[i]); visited[i] = 1; dfs(nums, vv, v, visited, level+1); v.pop_back(); visited[i] = 0; } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> vv; vector<int> v, visited(nums.size(),0); sort(nums.begin(), nums.end()); dfs(nums, vv, v, visited, 0); return vv; } };
Solution 3 ()
class Solution { public: void dfs(vector<int> nums, set<vector<int>>& sv, int level) { if(level >= nums.size()) { sv.insert(nums); return; } for(int i=level; i<nums.size(); ++i) { if(i != level && nums[i] == nums[level]) continue; swap(nums[i], nums[level]); dfs(nums, sv, level+1); swap(nums[i], nums[level]); } } vector<vector<int>> permuteUnique(vector<int>& nums) { set<vector<int>> sv; vector<int> v, visited(nums.size(),0); sort(nums.begin(), nums.end()); dfs(nums, sv, 0); return vector<vector<int>> (sv.begin(), sv.end()); } };
Solution 4 ()
class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> ans; vector<int> aux(nums.begin(), nums.end()); sort(aux.begin(), aux.end()); do { ans.emplace_back(aux.begin(), aux.end()); } while(next_permutation(aux.begin(), aux.end())); return ans; } };
【LeetCode】047. Permutations II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。