47. Permutations II
难度:Medium
刷题内容
原题连接
- https://leetcode.com/problems/permutations-ii/
内容描述
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
˼·1 *- ʱ�临�Ӷ�: O(n!nlgn)*- �ռ临�Ӷ�: O(n)***
��ǰ����ǵ����е����ƣ����Բο�֮ǰ�Ľⷨ内容描述��֮ǰ����Ŀ����ֱ�Ӿ���setȥ���ˣ���Ȼͨ���ˣ�����ʱ�临�ӶȱȽϸߣ������Ҫ�����Ż�
class Solution {
public:
void DFS(int* visited,vector<int>& nums,set<vector<int> >& ans,vector<int> temp)
{
int count1 = 0;
for(int i = 0;i < nums.size();++i)
if(!visited[i])
{
temp.push_back(nums[i]);
visited[i] = 1;
DFS(visited,nums,ans,temp);
temp.pop_back();
visited[i] = 0;
count1 = 1;
}
if(!count1)
ans.insert(temp);
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int> > ans;
int visited[nums.size()];
memset(visited,0,sizeof(visited));
set<vector<int> > s;
vector<int> temp;
for(int i = 0; i < nums.size();++i)
{
visited[i] = 1;
temp.push_back(nums[i]);
DFS(visited,nums,s,temp);
temp.pop_back();
visited[i] = 0;
}
for(auto pos = s.begin();pos != s.end();++pos)
ans.push_back(*pos);
return ans;
}
};
˼·2 **- ʱ�临�Ӷ�: O(n!)*- �ռ临�Ӷ�: O(n)***
����֮ǰ�ǵ���ľ��顣����Ҳ����ͨ��DFS�ķ���ȥ�⣬�����и����⣬����ͬ�����־ͻ�����ظ�������ȶ内容描述内容描述��ͬ�����־ͻ������һ��Ȼ�����DFSʱ内容描述���Ǵ������ҽ��еģ���˵�һ������֮ǰ������Ȳ���֮ǰ�������Ѿ内容描述ˣ���ô���ǾͲ内容描述内容描述
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
const int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
vector<int> visited(n, 0), arr;
dfs(nums, ret, arr, visited);
return ret;
}
void dfs(vector<int>& nums, vector<vector<int>>& ret, vector<int>& arr, vector<int>& visited) {
if (arr.size() == nums.size()) {
ret.push_back(arr);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (visited[i]) {continue;}
if (i -1 >= 0 && nums[i] == nums[i-1] && !visited[i-1]) {continue;}
arr.push_back(nums[i]);
visited[i] = 1;
dfs(nums, ret, arr, visited);
arr.pop_back();
visited[i] = 0;
}
}
};
