【Day 82 】2023-01-21 - 47 全排列 II

[azl397985856]

47 全排列 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/permutations-ii/

前置知识

• 回溯
• 数组
• 剪枝

题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]

[snmyj]

class Solution {
public:
    void help(int pos,vector<vector<int>>&ans,vector<int>& nums){
        if(pos>nums.size()){
            return;
        }
        
        if(pos==nums.size()-1){
		
		
            for(int i=0;i<ans.size();i++){
                if(ans[i]==nums){
                    return;
                }
            }
            ans.push_back(nums);
            return;
        }
        
        for(int i=pos;i<nums.size();i++){
            swap(nums[i],nums[pos]);
            help(pos+1,ans,nums);
			
			
            swap(nums[i],nums[pos]);
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
      
        vector<vector<int>>ans;
      
        help(0,ans,nums);
        return ans;
    }
};

[guowei0223]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        used = [0] * len(nums)
        nums.sort()
        def backtrack(nums, used):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i] == 1:
                    continue
                if i > 0 and nums[i] == nums[i -1] and used[i-1] == 0:
                    continue
                path.append(nums[i])
                used[i] = 1
                backtrack(nums,used)
                path.pop()
                used[i] = 0
        backtrack(nums, used)
        return res

[mayloveless]

思路

回溯，因为有重复数字，需要用visited记录下是否选过了。

代码

var permuteUnique = function(nums) {
    nums = nums.sort((a,b) => a-b);// 把重复的放在一起。
    const res = [];
    // 因为数字相同的index不同，不能简单通过值排除，所以记录index是否入选了
    const visited = []
    var combineFunc = function(path) {
        if (path.length === nums.length) {
            res.push([...path]);
            return;
        }
        for (let i = 0;i<nums.length;i++) {
            // index i 已入选则不递归，保证重复数字都能入选
            if (visited[i] === 1) continue;
            // 保持相同数字的顺序，前面的数字没选上，后面相同的不能选
            // 避免只重复的相互交换了顺序：112和112其实是一样的
            if (i !==0 && nums[i] === nums[i-1] && visited[i-1] === 0) continue;
            visited[i] = 1;
            path.push(nums[i]);
            combineFunc([...path])
            path.pop();
            visited[i] = 0;
        }
    }
    combineFunc([]);
    return res;
};

复杂度

时间：O(n! )
空间：O(n! *n )

[Abby-xu]

class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ans = [[]]
for n in nums:
new_ans = []
for l in ans:
for i in range(len(l)+1):
new_ans.append(l[:i]+[n]+l[i:])
if i<len(l) and l[i]==n: break #handles duplication
ans = new_ans
return ans

[bookyue]

code

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>(n * n);
        dfs(nums, new boolean[n], new ArrayDeque<>(n), ans);
        return ans;
    }

    private void dfs(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]
                    || (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]))
                continue;

            used[i] = true;
            path.addLast(nums[i]);
            dfs(nums, used, path, ans);
            path.removeLast();
            used[i] = false;
        }
    }

[Ryanbaiyansong]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        n = len(nums)
        used = [False] * n
        nums.sort()
        def dfs(start: int) -> None:
            if start == n:
                res.append(path[:])
                return 
            
            for i in range(n):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                    continue
                path.append(nums[i])
                used[i] = True
                dfs(start + 1)
                path.pop()
                used[i] = False 
        
        dfs(0)
        return res


        # 1
        # 1 
        # 2

            

[FlipN9]

/**
    **核心在于**: 在 idx 上, 只填入 nums[i] 一次, 避免重复

    Approach 2: swap: 不断把所有可选择的数 换到当前位置
    
    TC: O(N * N!)
    SC: O(N)
*/
public class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;
    int N;
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        // if (nums == null || nums.length==0) 
        //     return res;
        this.nums = nums;
        this.N = nums.length;
        
        dfs(0);
        return res;
    }
    
    private void dfs(int idx) {
        if (idx == N) { 
            List<Integer> tmp = new ArrayList<>();
            for (int x: nums) { tmp.add(x); }
            res.add(tmp);
            return;
        }
        // 保证对于 在 idx 的位置上, 只会添加 nums[i] 一次
        Set<Integer> used = new HashSet<>();
        for (int i = idx; i < N; i++) {
            if (used.add(nums[i])) {
                swap(nums, idx, i);
                dfs(idx + 1);
                swap(nums, idx, i);
            }
        }
    }
    
    private void swap(int[] nums, int a, int b) {
        int x = nums[a];
        nums[a] = nums[b];
        nums[b] = x;
    }
}

/**
    Approach 1: 不断 loop 整个数组, 尝试使用未被使用的数, 加在 tmp 中

    如何避免重复? 在 填第idx个数时, 重复数字只填入一次
        x   x   x
        o   x   x
        o   o   x
        o   o   o
    为此需要对原数组排序, 保证相同的数字都相邻，
    然后每次填入的数一定是 这个数所在重复数集合 中「从左往右第一个未被填过的数字」
*/
class Solution1 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    
    int[] nums;
    int N;
    boolean[] visited;
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        this.nums = nums;
        this.N = nums.length;
        this.visited = new boolean[N];
        
        Arrays.sort(nums);
        dfs(0);
        return res;
    }
    
    // 不断 loop 整个数组, 尝试使用未被使用的数, 加在 tmp 中
    // idx 代表的是 现在讲新的数 添加进的 tmp 中的位置
    private void dfs(int idx) {
        if (idx == N) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < N; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])
                continue;
            if (!visited[i]) {
                visited[i] = true;
                tmp.add(nums[i]);
                dfs(idx + 1);
                visited[i] = false;
                tmp.remove(idx);
            }
        }
    }
}

[tiandao043]

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> index;
    unordered_map<int,bool> visited;
    void helper(vector<int>& nums, int level, unordered_map<int,bool>& visited){
        if(level==nums.size()){
            ans.push_back(index);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(visited[i]==false){
                if(i>0 && nums[i]==nums[i-1]&& !visited[i - 1]){
                    continue;
                }
                visited[i]=true;
                index.push_back(nums[i]);
                helper(nums,level+1,visited);
                index.pop_back();
                visited[i]=false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i++){
            visited[i]=false;
        }
        helper(nums,0,visited);
        // set<vector<int>> s(ans.begin(),ans.end());
        // ans.assign(s.begin(),s.end());
        return ans;
    }
};

O(N!∗op(res))，其中 N 是数组长度，op 操作即是昨天说的 res.add 算子的时间复杂度。
O(N∗N!)

[chenming-cao]

解题思路

回溯+剪枝。参考官方题解。因为我们要求排列，在排列中，每个元素只出现一次，所以我们使用一个visited数组来记录每个元素的被访问情况。去重和组合总和II的方法类似。先将数组排序，然后当遇到当前元素和之前一个元素相等并且前一个元素已经被访问过时，我们跳过当前元素。

代码

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, list, res, visited);
        return res;
    }

    private void backtrack(int[] nums, List<Integer> list, List<List<Integer>> result, boolean[] visited) {
        // if the length of list is equal to the length of nums, we find one permutation
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            // when the current element is equal to previous element and previous element is visited
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1]) {
                continue;
            }
            // in permutation, one element will only show up once, if this element is visited, we will skip it
            // if this element is not visited, continue backtracking to add another element
            if (!visited[i]) {
                visited[i] = true;
                list.add(nums[i]);
                backtrack(nums, list, result, visited);
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n! * op(res))，n为数组长度
• 空间复杂度：O(n * n!)

[paopaohua]

public List<List<Integer>> permuteUnique(int[] nums) {

    List<List<Integer>> res = new ArrayList<>();

    if (nums == null || nums.length == 0)
        return res;

    boolean[] visited = new boolean[nums.length];
    Arrays.sort(nums);
    dfs(nums, res, new ArrayList<Integer>(), visited);

    return res;
}

public void dfs(int[] nums, List<List<Integer>> res, List<Integer> tmp, boolean[] visited) {

    if (tmp.size() == nums.length) {

        res.add(new ArrayList(tmp));
        return;
    }
    for (int i = 0; i < nums.length; i++) {

        if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])
            continue;
        if (!visited[i]) {

            visited[i] = true;
            tmp.add(nums[i]);
            dfs(nums, res, tmp, visited);
            visited[i] = false;
            tmp.remove(tmp.size() - 1);
        }
    }

[Elsa-zhang]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(ans, temptlist, nums, check):
            if len(temptlist) == len(nums):
                return ans.append(temptlist[:])
            
            for i in range(len(nums)):
                if check[i] == 1:
                    continue
                if i>0 and nums[i]==nums[i-1] and check[i-1] == 0:
                    continue
                    
                check[i] = 1
                temptlist.append(nums[i])

                dfs(ans,temptlist,nums,check)

                temptlist.pop()
                check[i] = 0
        
        nums = sorted(nums)
        temptlist = []
        ans = []
        check = [0]*len(nums)
        dfs(ans, temptlist, nums, check)
        return ans

[klspta]

public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>(n * n);
        dfs(nums, new boolean[n], new ArrayDeque<>(n), ans);
        return ans;
    }

    private void dfs(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]
                    || (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]))
                continue;

            used[i] = true;
            path.addLast(nums[i]);
            dfs(nums, used, path, ans);
            path.removeLast();
            used[i] = false;
        }
    }