LeetCode 47. Permutations II (Java版; Meidum)

曾经终败给现在 2023-07-21 11:27 4阅读 0赞

### [welcome to my blog][] ###

## LeetCode 47. Permutations II (Java版; Meidum) ##

#### 题目描述 ####

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) 递归函数逻辑: 处理完\[0,i\], 当前处理索引i处的元素; \[i,n-1\]范围上的元素都没用过; HashSet去重, 防止索引i处使用重复的元素 ####

class Solution { 
        public List<List<Integer>> permuteUnique(int[] nums) { 
            List<List<Integer>> list = new ArrayList<>();
            List<Integer> al = new ArrayList<>();
            core(list, al, nums, 0);
            return list;
        }
    
        //递归函数逻辑: [0,i]上的结果
        private void core(List<List<Integer>> list, List<Integer> al, int[] nums, int i){ 
            //base case
            if(i==nums.length){ 
                list.add(new ArrayList<Integer>(al));
                return;
            }
            //
            int index=i;
            //记录当前位置出现过的数字
            HashSet<Integer> set = new HashSet<>();
            for(int k=i; k<nums.length; k++){ 
                int cur = nums[k];
                if(set.contains(cur)){ 
                    continue;
                }
                swap(nums, index, k);
                al.add(cur);
                set.add(cur);
                core(list, al, nums, i+1);
                //
                al.remove(al.size()-1);
                swap(nums, index, k);
            }
        }
    
        private void swap(int[] arr, int i, int j){ 
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

[welcome to my blog]: https://littlehaes.com