Skip to content

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;
        }
    }
};


回到顶部