首页 > 代码库 > 【LeetCode】047. Permutations II

【LeetCode】047. Permutations II

2024-09-20 06:31:23   216人阅读

题目：

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


联系
我们