Only for Share 【java accepted】


  • 0
    E

    I got TEL first by removing the duplication after it has generated the duplication. Then, I change my mind,
    If we can avoid generating the duplication, will the method be faster. Keep this in mind, here is my algorithm. I first sort the input array, then by recursive algorithm permute the array, but each unique number only permute once. the code is here:

    /**
      * Given a collection of numbers, return all possible permutations.
      * @param num
      * @return
      * @author huangting
      * @date 2014-7-1
      */
     private List<List<Integer>> permute(int[] num) {
    	//because we have to delete from the array, so we first transfer
    	 //to the linkedlist
    	 LinkedList<Integer> n = new LinkedList<Integer>() ; 
    	 for(int i=0;i<num.length;i++){
    		 n.add(num[i]);
    	 }
    	 return permuteDetail(n);
     }
     /**
      * by recursive algorithm, I do the permutation
      * @param num
      * @return
      * @author huangting
      * @date 2014-7-1
      */
     private List<List<Integer>> permuteDetail(LinkedList<Integer> num) {
    	 List<List<Integer>> ret = new ArrayList<List<Integer>>();
    	 if(num == null || num.size()<=0)
    		 return ret;
    	 if(num.size() == 1){
    		 ArrayList<Integer> curr = new ArrayList<Integer>();
    		 curr.add(num.get(0));
    		 ret.add(curr);
    		 return ret;
    	 }
    	 int last = Integer.MAX_VALUE;
    	 for(int i=0;i<num.size();i++){
    		 //since we have sort the array, if the next one is the same with the last
    		 //one, it will get the same permutation, so we don't need to permute it
    		 if(num.get(i) == last)
    		 {
    			 continue;
    		 }
    		 //track the last one num
    		 last = num.get(i);
    		 int cur = num.get(i);
    		 LinkedList<Integer> newNum = new LinkedList<Integer>();
    		 newNum.addAll(num);
    		 
    		 last = newNum.get(i);
    		 newNum.remove(i);
    		 List<List<Integer>> sub = permuteDetail(newNum);
    		 //merge
    		 for(int j=0;j<sub.size();j++){
    			sub.get(j).add(cur);
    			ret.add(sub.get(j));
    		 }
    	 }
    	return ret;
     }
     public List<List<Integer>> permuteUnique(int[] num) {
    	 Arrays.sort(num);//first sort,so we can avoid the duplication by not generating it
    	 return permute(num);
      }

  • 1
    W

    I have a more elegant code which is change from permutation I to permutation II.But maybe the method to remove duplicated is not so efficient.I think hashtable will be change the satuation.

    class Solution {
    public:
    //why output limit exceed!!!???can't find the reason!!!
    vector<vector<int> > ans;
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(),num.end());
        dfs(num,0);
        return ans;
    }
    void dfs(vector<int> &num,int start) {
        //step 1
        if(start == num.size()) {
            ans.push_back(num);
            return;
        }
        //step 2
        
        //step 3
        for(int i = start;i < num.size();i++) {
            //skip duplicate,if the element have emerge before,skip this one!!!
            bool skip = false;
            for(int j = start;j < i;j++) {
                if(num[j] == num[i]) {
                    skip = true;
                    break;
                }
            }
            if(skip)
                continue;
            //if before have be meeted,so skip this???maybe hashtable will be more efficient???
            swap(num[i],num[start]);
            dfs(num,start+1);
            swap(num[i],num[start]);
        }
    }
    

    };


Log in to reply
 

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