描述
給出一個具有重復數(shù)字的列表肮街，找出列表所有不同的排列
樣例
給出列表 [1,2,2]熏挎，不同的排列有：
[
[1,2,2],
[2,1,2],
[2,2,1]
]
注意
去重的寫法凝垛，定義visited數(shù)組來記錄是否被添加，因為相同值的nums[i - 1]和nums[i]用list.contains(nums[i - 1])并不能區(qū)分list里面到底加入的是哪一個炸渡，起不到去重效果
代碼
public class Solution {
/*
* @param nums: A list of integers
* @return: A list of unique permutations
*/
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null) {
return results;
}
if (nums.length == 0) {
results.add(new ArrayList<Integer>());
return results;
}
// 注意先要對nums排序，因為答案對題目有順序要求
Arrays.sort(nums);
ArrayList<Integer> list = new ArrayList<>();
// 不要忘記將visit數(shù)組初始化為0,visit為整型
int[] visited = new int[nums.length];
for (int i = 0; i < visited.length; i++) {
visited[i] = 0;
}
helper(nums, list, results, visited);
return results;
}
private void helper(int[] nums,
List<Integer> list,
List<List<Integer>> results,
int[] visited) {
if (list.size() == nums.length) {
results.add(new ArrayList<Integer>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
/* 下面的判斷主要是為了去除重復元素影響丽已。
* 比如蚌堵，給出一個排好序的數(shù)組，[1,2,2]沛婴，那么第一個2和第二2如果在結果中互換位置吼畏，
* 我們也認為是同一種方案，所以我們強制要求相同的數(shù)字嘁灯，原來排在前面的泻蚊，在結果
* 當中也應該排在前面，這樣就保證了唯一性丑婿。所以當前面的2還沒有使用的時候性雄，就
* 不應該讓后面的2使用。
*/
// 去除重復元素影響選代表以及訪問過的元素就不要繼續(xù)添加了
if (visited[i] == 1 || (i != 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0)) {
continue;
}
list.add(nums[i]);
visited[i] = 1;
helper(nums, list, results, visited);
list.remove(list.size() - 1);
visited[i] = 0;
}
}
}
本題的去重條件if (visited[i] == 1 || (i != 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0))中visited[i] == 1實際上就相當于全排列的判斷條件if (list.contains(nums[i]))枯冈， 而后面的(i != 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0)實際上是在除下列情況：比如數(shù)組 [1, 2, 2] 第一個 2 用 A 表示毅贮，第二個 2 用 B 表示，我們在 [1, A, B] 和 [1, B, A] 兩個相同排序中選取典型的[1, A, B]做代表尘奏，所以當某一次遞歸出現(xiàn) [1, B] 開頭的排序滩褥，下一個遞歸中只有 A 未被添加，但我們通過判斷條件(i != 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0) continue 掉 A
