Share my method ( Transformed from Permutations I, only add two lines of codes)


  • 2
    S

    Update:

    Actually, according the recuisive schema showed in below codes, we just need to make sure same elements only get operated once, then we can get right answer, this can be done via a HashSet: if this set.containsKey(elem) is false, do the operation and put it in, otherwise skip this elem.

    This piece of codes is fit for both Permutaiton I and II.

    Thanks for GuaGua's remind. Here is the new code:

    public class PermutationsII {
    	public List<List<Integer>> permuteUnique(int[] num) {
    		if(num == null || num.length == 0) return new ArrayList<List<Integer>>();
    		else {
    			List<Integer> list = new ArrayList<Integer>();
    			for(int i = 0; i < num.length; i ++) list.add(num[i]);
    			return permute(list);
    		}
    	}
    	    
    	public List<List<Integer>> permute(List<Integer> num) {
    		if(num.size() == 0) {
    			List<List<Integer>> result = new ArrayList<List<Integer>>();
    			result.add(new ArrayList<Integer>());
    			return result;
    		} else {
    			List<List<Integer>> result = new ArrayList<List<Integer>>();
    			Set<Integer> replica = new HashSet<Integer>();
    			for(int i = 0; i < num.size(); i ++) {
    				int tmp = num.get(i);
    				if(!replica.contains(tmp)) {
    					replica.add(tmp);
    					num.remove(i);
    					List<List<Integer>> tmpResult = permute(num);
    					for(List<Integer> elem : tmpResult) {
    						elem.add(0, tmp);
    						result.add(elem);
    					}
    						num.add(i, tmp);
    				}
    			}
    			return result;
    		}
    	}
    }
    

    ---- old content ----
    I add only 2 lines of codes to make the solution of Permutation I also fit for II.

    Solution for Permutation I:

    1, Put the array into a list

    2, Remove one element in this list, save it as variable elem, get permutations of all other elements, then put this elem in the head of every permutation of other elements. Do this to every element of list, collect all results and return.

    Solution for II(differences has been marked bold):

    1, Put the array into a list, and sort;

    2, Do that(refer to step 2 of Permutation I) only once for same elements.

    Codes added:

    1, Arrays.sort(num); // sort

    2, if(i == 0 || tmp != num.get(i - 1)) {...} // add a condition so same elements only be processed once

    Complete Codes(ACCEPTED):

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] num) {
            if(num == null || num.length == 0) return new ArrayList<List<Integer>>();
    		else {
    			Arrays.sort(num);
    			List<Integer> list = new ArrayList<Integer>();
    			for(int i = 0; i < num.length; i ++) list.add(num[i]);
    			return permute(list);
    		}
        }
        
        public List<List<Integer>> permute(List<Integer> num) {
    		if(num.size() == 0) {
    			List<List<Integer>> result = new ArrayList<List<Integer>>();
    			result.add(new ArrayList<Integer>());
    			return result;
    		}
    		else {
    			List<List<Integer>> result = new ArrayList<List<Integer>>();
    			for(int i = 0; i < num.size(); i ++) {
    				int tmp = num.get(i);
    				if(i == 0 || tmp != num.get(i - 1)) {
    					num.remove(i);
    					List<List<Integer>> tmpResult = permute(num);
    					for(List<Integer> elem : tmpResult) {
    						elem.add(0, tmp);
    						result.add(elem);
    					}
    					num.add(i, tmp);
    				}
    			}
    			return result;
    		}
    	}
    }

  • 0
    H
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with elaborated thoughts. Please read the FAQ for more info. Take a look at good sharing example


  • 2
    G

    The method can be improved by using a hash map instead of sorted list.

    • 1, Construct a hash map from the input array. The hash map maps each
      distinct value to its frequency. For instance, if there are three 1's
      in the array, in the hash map it would be 1=>3.

    • 2, Get the permutations with a recursive scheme.
      For each key value in the hash map:
      subtract its frequency by 1; get the permutations from the new map and put the key to the head of those permutations; restore its frequency(+1); if the frequency is 0, just skip.

    The code can be applied to both Permutations I and Permutations II without any changes.


  • 0
    S

    Thanks for your comment. Actually, I've came up with another idea after got your comment.

    We don't even need to build a Map, we just need a Set with this recursive schema: if current element is not contained in the set, do the operation and put it in, or skip.

    Also, this piece of code is fit for Permutation I problem

    Code passed.

    Thanks!~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.