A java iterative solution, not so fast, can someone optimize it?


  • 0
    C

    quite same as the permutation I popular solution, the difference here is that we only insert the nums[i] to a latter position. E.g. the i-1 has a [1,2,2,1] and we need to insert 2, we only insert it at [1,2,2,here,1] and [1,2,2,1,here].

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            if(nums.length == 0) return result;
            List<Integer> l0 = new ArrayList<Integer>();
            l0.add(nums[0]);
            result.add(l0);
            for(int i=1; i<nums.length; i++){
                List<List<Integer>> newans = new ArrayList<List<Integer>>();
                for(List<Integer> temp : result){
                    int key = 0;
                    for(int j = 0; j<temp.size(); j++){
                        if(temp.get(j)==nums[i]){
                           key = j+1; 
                        }
                    }
                    for(int j =key;j<=i; j++){
                        List newl = new ArrayList<Integer>(temp);
                        newl.add(j, nums[i]);
                        newans.add(newl);
                    }
                }
                result = newans;
            }
            return result;
        }
    }
    

Log in to reply
 

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