leetcode--Permutations II-蒲公英云

leetcode--Permutations II

Dear 丶 2021-10-25 12:38 374阅读 0赞

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], and [2,1,1].

public class Solution {
    /**
     * To obtain a new permutation, given a permutation, we need to implement a series of swaps between 
     * two indices. All swaps are represented by indices as the following form (i, j), where i <= j.<br>
     * So, in order to get all permutations, we only need to implements O(n^2) swaps. 
     * @param num -int array
     * @return List<List<Integer> > -all permutations
     * @author Averill Zheng
     * @version 2014-06-24
     * @since JDK 1.7
     */
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer> > result = new ArrayList<List<Integer> >();
        int length = num.length;
        if(length > 0){
            List<Integer> startPermutation = new ArrayList<Integer>();
            for(int s : num)
                startPermutation.add(s);
            result.add(startPermutation);
            //classify all swaps into groups(1, j), (2, j), ...(length - 2, j)
            for(int i = 0; i < length - 1; ++i){
                List<List<Integer> > tempResult = new ArrayList<List<Integer> >();
                while(!result.isEmpty()){
                    List<Integer> oldPermutation = result.remove(0);
                    //use a HashSet to record the duplications.
                    Set<Integer> alreadySwapped = new HashSet<Integer>();
                    //j starts from i, NOT i + 1, because we need to save original permutation back to tempResult
                    for(int j = i; j < length; ++j) {
                        if(!alreadySwapped.contains(oldPermutation.get(j))) {
                            List<Integer> newListBySwapping = new ArrayList<Integer>();
                            newListBySwapping.addAll(oldPermutation);
                            //swap oldPermutation.get(i) and oldPermutation.get(j)
                            int valueAtJ = oldPermutation.get(j);
                            newListBySwapping.set(j, oldPermutation.get(i));
                            newListBySwapping.set(i, valueAtJ);
                            alreadySwapped.add(valueAtJ);
                            tempResult.add(newListBySwapping);
                        }
                    }
                }
                result = tempResult;
            }
        }
        return result;
    }
}