47. Permutations II

向右看齐 2022-03-07 10:36 177阅读 0赞

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]
    ]

难度：medium

题目：给定一组可能包含重复数的集合，返回所有可能的排列。

思路：先对数组进行排序，为去重做准备。然后借助递归遍历所有数。重点在于，当每次选定一个数做完交换之后，恢复时要对两个交换数及之间的所有数做排序。继续为接下来的去重做准备。

class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<>();
            permuteUnique(nums, 0, new Stack<Integer>(), result);
            
            return result;
        }
        
        private void permuteUnique(int[] nums, int idx, Stack<Integer> stack, List<List<Integer>> result) {
            if (idx == nums.length) {
                result.add(new ArrayList<>(stack));
                return;
            }
            
            for (int i = idx; i < nums.length; i++) {
                if (idx == i || nums[i] != nums[i - 1]) {
                    stack.push(nums[i]);
                    swap(nums, idx, i);
                    permuteUnique(nums, idx + 1, stack, result);
                    swap(nums, i, idx);
                    Arrays.sort(nums, idx, i + 1);
                    stack.pop();
                }
            }
        }
    
        private void swap(int[] nums, int i, int j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关 47. 全排列 II

> 关上过去和未来的铁门，活在“今天”这个舱室中。——《人性的优点》 47. 全排列 II 给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列

系统管理员/ 2024年03月31日 14:52/ 0 赞/ 108 阅读

相关 LeetCode 47. Permutations II (Java版; Meidum)

[welcome to my blog][] LeetCode 47. Permutations II (Java版; Meidum) 题目描述 Gi

曾经终败给现在/ 2023年07月21日 11:27/ 0 赞/ 4 阅读

相关 LeetCode - Medium - 47. Permutations II

Topic Backtracking Description [https://leetcode.com/problems/permutations-ii/

喜欢ヅ旅行/ 2023年01月13日 10:25/ 0 赞/ 99 阅读

相关 Permutations II（C++全排列 II）

（1）递归 class Solution { private: vector<vector<int>> v; public:

ゝ一纸荒年。/ 2022年10月11日 00:44/ 0 赞/ 183 阅读

相关 LeetCode47——Permutations II

LeetCode47——Permutations II 含重复元素的全排列，仍然是套用了下一个全排列的方法。跟上题一样，有时间补上递归解法。代码： clas

清疚/ 2022年08月09日 12:41/ 0 赞/ 159 阅读

相关 Leetcode: Permutations II

题目： Given a collection of numbers that might contain duplicates, return all possible u

Bertha 。/ 2022年08月07日 15:59/ 0 赞/ 139 阅读

相关 Permutation II--LeetCode

Given a collection of numbers that might contain duplicates, return all possible unique

痛定思痛。/ 2022年08月07日 11:46/ 0 赞/ 93 阅读

相关 leetcode 47. Permutations II 全排列问题（去掉重复元素）+递归

Given a collection of numbers that might contain duplicates, return all possible unique

野性酷女/ 2022年06月09日 10:19/ 0 赞/ 235 阅读

相关 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique

向右看齐/ 2022年03月07日 10:36/ 0 赞/ 178 阅读

相关 leetcode--Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique

Dear 丶/ 2021年10月25日 12:38/ 0 赞/ 287 阅读