題目描述（中等難度）
和上一道題類似，不同之處就是給定的數(shù)字中會有重復(fù)的，這樣的話用之前的算法會產(chǎn)出重復(fù)的序列。例如，[ 1 1 ]，用之前的算法，產(chǎn)生的結(jié)果肯定是 [ [ 1 1 ]， [ 1 1 ] ]，也就是產(chǎn)生了重復(fù)的序列。但我們可以在上一題的解法中進(jìn)行修改從而解決這道題。
解法一 插入
這個沒想到怎么在原基礎(chǔ)上改，可以直接了當(dāng)些，在它產(chǎn)生的結(jié)果里，對結(jié)果去重再返回。對于去重的話，一般的方法肯定就是寫兩個 for 循環(huán)，然后一個一個互相比較，然后找到重復(fù)的去掉。這里，我們用 39題 解法二中提到的一種去重的方法。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> all = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
temp.add(nums[0]);
all.add(temp);
for (int i = 1; i < nums.length; i++) {
int current_size = all.size();
for (int j = 0; j < current_size; j++) {
List<Integer> last = all.get(j);
for (int k = 0; k <= i; k++) {
if (k < i && nums[i] == last.get(k)) {
continue;
}
temp = new ArrayList<>(last);
temp.add(k, nums[i]);
all.add(temp);
}
}
for (int j = 0; j < current_size; j++) {
all.remove(0);
}
}
return removeDuplicate(all);
}
private List<List<Integer>> removeDuplicate(List<List<Integer>> list) {
Map<String, String> ans = new HashMap<String, String>();
for (int i = 0; i < list.size(); i++) {
List<Integer> l = list.get(i);
String key = "";
// [ 2 3 4 ] 轉(zhuǎn)為 "2,3,4"
for (int j = 0; j < l.size() - 1; j++) {
key = key + l.get(j) + ",";
}
key = key + l.get(l.size() - 1);
ans.put(key, "");
}
// 根據(jù)逗號還原 List
List<List<Integer>> ans_list = new ArrayList<List<Integer>>();
for (String k : ans.keySet()) {
String[] l = k.split(",");
List<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < l.length; i++) {
int c = Integer.parseInt(l[i]);
temp.add(c);
}
ans_list.add(temp);
}
return ans_list;
}
解法二 回溯
看下之前的算法
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), nums);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue; // 已經(jīng)存在的元素，跳過
tempList.add(nums[i]); //將當(dāng)前元素加入
backtrack(list, tempList, nums); //向后繼續(xù)添加
tempList.remove(tempList.size() - 1); //將 tempList 剛添加的元素，去掉，嘗試新的元素
}
}
}
假如給定的數(shù)組是 [ 1 1 3 ]，我們來看一下遍歷的這個圖。
第一個要解決的就是這句代碼
if(tempList.contains(nums[i])) continue; // 已經(jīng)存在的元素，跳過
之前沒有重復(fù)的元素，所以可以直接在 templist 判斷有沒有當(dāng)前元素，有的話就跳過。但這里的話，因為給定的有重復(fù)的元素，這個方法明顯不可以了。
換個思路，我們可以再用一個 list 保存當(dāng)前 templist 中已經(jīng)有的元素的下標(biāo)，然后添加新元素的時候去判斷下標(biāo)就可以了。
第二個問題就是，可以看到有重復(fù)元素的時候，上邊第 1 個圖和第 2 個圖產(chǎn)生的是完全一樣的序列。所以第 2 個遍歷是沒有必要的。
解決的方案就是把數(shù)組首先排下順序，然后判斷一下上一個添加的元素和當(dāng)前元素是不是相等，相等的話就跳過，繼續(xù)下一個元素。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
List<Integer> old = new ArrayList<>();
backtrack(list, new ArrayList<>(), nums, old);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, List<Integer> old) {
if (tempList.size() == nums.length) {
list.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
//解決第一個問題
if (old.contains(i)) {
continue;
}
//解決第二個問題 !old.contains(i - 1) 很關(guān)鍵，下邊解釋下
if (i > 0 && !old.contains(i - 1) && nums[i - 1] == nums[i]) {
continue;
}
old.add(i);//添加下標(biāo)
tempList.add(nums[i]); // 將當(dāng)前元素加入
backtrack(list, tempList, nums, old); // 向后繼續(xù)添加
old.remove(old.size() - 1);
tempList.remove(tempList.size() - 1);
}
}
}
解決第二個問題 !old.contains(i - 1) 很關(guān)鍵
因為上邊 old.contains(i) 代碼會使得一些元素跳過沒有加到 templist 上，所以我們要判斷 nums[ i - 1 ] 是不是被跳過的那個元素，如果 old.contains ( i ) 返回 true ， 即使 nums [ i - 1 ] == nums [ i ] 也不能跳過當(dāng)前元素。因為上一個元素 nums [ i - 1 ] 并沒有被添加到 templist。可能比較繞，但是可以參照上邊的圖，走一下流程就懂了。如果不加 !old.contains ( i - 1 )，那么圖中的第 2 行的第 2 個 1 本來應(yīng)該加到 tempList，但是會被跳過。因為第 2 行第 1 個元素也是 1。
對于解決第一個問題，我們用了一個 list 來保存下標(biāo)來解決。需要一個 O ( n ) 的空間。有一種方法，我們可以用 O（1）的空間。不過前提是，我們需要對問題的樣例了解，也就是給定的輸入所包含的數(shù)字。我們需要找到一個樣例中一定不包含的數(shù)字來解決我們的問題。
首先，我們假設(shè)輸入的所有的數(shù)字中沒有 -100 這個數(shù)字。
然后，我們就可以遞歸前將當(dāng)前數(shù)字先保存起來，然后置為 -100 隱藏起來，遞歸結(jié)束后還原即可。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
if (tempList.size() == nums.length) {
list.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
//解決第一個問題
if (nums[i] == -100) {
continue;
}
//解決第二個問題 !old.contains(i - 1) 很關(guān)鍵
if (i > 0 && nums[i-1] != -100 && nums[i - 1] == nums[i]) {
continue;
}
tempList.add(nums[i]); // 將當(dāng)前元素加入
int temp = nums[i]; //保存
nums[i] = -100; // 隱藏
backtrack(list, tempList, nums); // 向后繼續(xù)添加
nums[i] = temp; //還原
tempList.remove(tempList.size() - 1);
}
}
}
當(dāng)然這個想法局限性很大，但是如果對解決的問題很熟悉，一般是可以找到這樣一個不會輸入的數(shù)字，然后可以優(yōu)化空間復(fù)雜度。
解法三 交換
這個改起來相對容易些，之前的想法就是在每一個位置，讓每個數(shù)字輪流交換過去一下。這里的話，我們其實只要把當(dāng)前位置已經(jīng)有哪些數(shù)字來過保存起來，如果有重復(fù)的話，我們不讓他交換，直接換下一個數(shù)字就可以了。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> all = new ArrayList<>();
Arrays.sort(nums);
upset(nums, 0, all);
return all;
}
private void upset(int[] nums, int begin, List<List<Integer>> all) {
if (begin == nums.length) {
ArrayList<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
temp.add(nums[i]);
}
all.add(new ArrayList<Integer>(temp));
return;
}
HashSet<Integer> set = new HashSet<>(); //保存當(dāng)前要交換的位置已經(jīng)有過哪些數(shù)字了
for (int i = begin; i < nums.length; i++) {
if (set.contains(nums[i])) { //如果存在了就跳過，不去交換
continue;
}
set.add(nums[i]);
swap(nums, i, begin);
upset(nums, begin + 1, all);
swap(nums, i, begin);
}
}
private void swap(int[] nums, int i, int begin) {
int temp = nums[i];
nums[i] = nums[begin];
nums[begin] = temp;
}
總
基本上都是在上道題的基礎(chǔ)上改出來了，一些技巧也是經(jīng)常遇到，比如先排序，然后判斷和前一個是否重復(fù)。利用 Hash 去重的功能。利用原來的存儲空間隱藏掉數(shù)據(jù)，然后再想辦法還原。
更多詳細(xì)通俗題解詳見 leetcode.wang 。
