leetcode--Permutations II

Dear 丶 2021-10-25 12:38 269阅读 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;
        }
    }

转载于:https://www.cnblogs.com/averillzheng/p/3542227.html