leetcode47-Permutations II

分析

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

题目

由于元素是重复的，要求返回不重复的，所以一定会有剪枝的动作，具体的思路就是给数组排序，然后发现上一个元素和当前元素一样的话就没必要再遍历了。这里需要注意的是剪枝不能解决掉所有的重复元素的问题，比如0,0,0,1,9这样的序列，在第0个元素求解完以后递归求解第1个元素的时候，由于俩个元素都是0所以肯定会发生重复，所以这里可以再用一个set来存储全排序列

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;public class permutationsII {private static Set<List<Integer>> set = new HashSet();public static void main(String[] args) {int[] arr = {0,1,0,0,9};Arrays.sort(arr);getRank(arr,0,arr.length);List<List<Integer>> res = new ArrayList();res.addAll(set);for(List<Integer> lis : res) {for(Integer data:lis) {System.out.print(data + " ");}System.out.println();}}public static void getRank(int[] nums,int start,int len) {if(start + 1 == len) {List<Integer> lis = new ArrayList();for(int i = 0;i<len;i++) {lis.add(nums[i]);}set.add(lis);return;}for(int i = start;i<len;i++) {if(start < i && nums[i-1] == nums[i]) {continue;}int tmp = nums[start];nums[start] = nums[i];nums[i] = tmp;getRank(nums,start+1,len);tmp = nums[start];nums[start] = nums[i];nums[i] = tmp;}}
}