LintCode 16. 帶重復元素的排列

寫在前面：這題和全排列不含重復元素的那題幾乎一樣，我比較垃圾，就用HashSet去掉了重復的元素但是看了九章算法的答案也沒看懂，他寫的很有感覺。

用了hash，本來想著怎么寫hashcode()和equal()方法的，哪知道都幫我寫好了，Integer類型的元素存儲在List中的hashcode()和equal()的方法可以直接使用
下面是源代碼和我的測試代碼：

//這是ArrayList父類public abstract class AbstractList<E>中的源碼
public int hashCode() {int hashCode = 1;for (E e : this)hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());return hashCode;}public boolean equals(Object o) {if (o == this)return true;if (!(o instanceof List))return false;ListIterator<E> e1 = listIterator();ListIterator<?> e2 = ((List<?>) o).listIterator();while (e1.hasNext() && e2.hasNext()) {E o1 = e1.next();Object o2 = e2.next();if (!(o1==null ? o2==null : o1.equals(o2)))return false;}return !(e1.hasNext() || e2.hasNext());}

@Testpublic void test() {List<Integer> list1 = new ArrayList<>();list1.add(1);List<Integer> list2 = new ArrayList<>();list2.add(2);List<Integer> list3 = new ArrayList<>();list3.add(1);System.out.println(list1.hashCode());System.out.println(list2.hashCode());System.out.println(list3.hashCode());System.out.println(list1==list2);System.out.println(list1==list3);System.out.println(list2==list3);System.out.println(list1.equals(list2));System.out.println(list1.equals(list3));System.out.println(list2.equals(list3));}
//運行結果
//        32
//        33
//        32
//        false
//        false
//        false
//        false
//        true
//        false

下面是我寫的代碼，只是使用HashSet去重

import org.junit.Test;import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;public class permuteUnique {/*** @param : A list of integers* @return: A list of unique permutations* <p>* 16. 帶重復元素的排列* 給出一個具有重復數字的列表，找出列表所有不同的排列。* <p>* 樣例* 給出列表 [1,2,2]，不同的排列有：* <p>* [* [1,2,2],* [2,1,2],* [2,2,1]* ]* 挑戰* 使用遞歸和非遞歸分別完成該題。* <p>* 寫過不含重復元素的全排列，這提是含重復元素的，應該相差不大*/public List<List<Integer>> permuteUnique(int[] nums) {// write your code hereHashSet<List<Integer>> hashResult = new HashSet<>();List<List<Integer>> result = new ArrayList<>();List<Integer> list = new ArrayList<>();if (nums == null) {return result;}if (nums.length == 0) {result.add(list);return result;}boolean[] color = new boolean[nums.length];for (int i = 0; i < nums.length; i++) {color[i] = false;}dfs(hashResult, list, nums, color);result = new ArrayList<>(hashResult);return result;}public void dfs(HashSet<List<Integer>> hashResult, List<Integer> list, int[] nums, boolean[] color) {if (list.size() == nums.length) {hashResult.add(new ArrayList<>(list));return;}for (int i = 0; i < nums.length; i++) {if (color[i] == false) {list.add(nums[i]);color[i] = true;dfs(hashResult, list, nums, color);color[i] = false;list.remove(list.size() - 1);}}}@Testpublic void testPermuteUnique() {
//        List<List<Integer>> result = permuteUnique(new int[]{1, 2, 2});
//        for (int i = 0; i < result.size(); i++) {
//            System.out.println(result.get(i).toString());
//        }}
}

---

下面是九章的答案，寫的很難懂，狠巧妙
和沒有重復元素的 Permutation 一題相比，只加了兩句話：

Arrays.sort(nums) // 排序這樣所有重復的數
if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } // 跳過會造成重復的情況

    public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> results = new ArrayList<>();if (nums == null) {return results;}Arrays.sort(nums);dfs(nums, new boolean[nums.length], new ArrayList<Integer>(), results);return results;}private void dfs(int[] nums,boolean[] visited,List<Integer> permutation,List<List<Integer>> results) {if (nums.length == permutation.size()) {results.add(new ArrayList<Integer>(permutation));return;}for (int i = 0; i < nums.length; i++) {if (visited[i]) {continue;}if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {continue;}permutation.add(nums[i]);visited[i] = true;dfs(nums, visited, permutation, results);visited[i] = false;permutation.remove(permutation.size() - 1);}}