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] ]题目：和上一题类似，只不过这题有重复的数字。
思路：还是上面的思路，只是存list的时候先判断一把，如果已经存在的就忽略。
public List<List<Integer>> permuteUnique(int[] nums){ List<List<Integer>> list1 = new ArrayList<List<Integer>>(); if(nums.length == 1) { List<List<Integer>> list = new ArrayList<List<Integer>>(); List<Integer> l = new ArrayList<Integer>(); l.add(nums[0]); list.add(l); return list; } int[] num1 = Arrays.copyOfRange(nums, 1, nums.length); int n = nums[0]; for(List<Integer> li : permuteUnique(num1)) { int[] num = listToArray(li); List<List<Integer>> noReapet = sort(num, n); for(List<Integer> l:noReapet) { if(!list1.contains(l)) { list1.add(l); } } } return list1; } public List<List<Integer>> sort(int[] nums, int num){ List<List<Integer>> list = new ArrayList<List<Integer>>(); for(int i = 0; i < nums.length+1;i++) { int[] n = new int[nums.length+1]; for(int k = 0 ; k < nums.length;k++) { n[k] = nums[k]; } int tmp = n[i]; n[i] = num; int j = n.length-1; for(;j > i+1;j--) { n[j] = n[j-1]; } if(i != j) { n[j] = tmp; } if(!list.contains(arrayToList(n))) { list.add(arrayToList(n)); } } return list; } public int[] listToArray(List<Integer> list){ int[] n = new int[list.size()]; int j = 0; for(Integer i:list){ n[j++] = i; } return n; } public List<Integer> arrayToList(int[] nums) { List<Integer> list = new ArrayList<Integer>(); for(int i = 0;i < nums.length;i++){ list.add(nums[i]); } return list; }
