Java Iterative solution, no Set needed!


  • 11
    S

    In each iteration, put the new number to all possible place.
    To avoid duplicate we also have to:

    1. For duplicate numbers in a row, only add same number in in front of them.
    2. Break when same number exists in the permutation.
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            LinkedList<List<Integer>> r = new LinkedList<>();
            r.add(new ArrayList<Integer>());
            for(int i=0; i<nums.length; i++){
                int n = r.size();
                for(int j=0; j<n; j++){
                    List<Integer> list = r.poll();
                    for(int k=0; k<=list.size(); k++){
                        if(k > 0 && list.get(k-1) == nums[i])
                            break;
                        ArrayList<Integer> t = new ArrayList<>(list);
                        t.add(k, nums[i]);
                        r.offer(t);
                    }
                }
            }
            return r;
        }
    }

  • 0

    Cool idea, but what's the run time? Three for loops and another O(n) operation of t.add(k, nums[i]) inside. And, am I correct in thinking that it is a type of BFS as opposed to more popular DFS solutions?


  • 1
    S

    The time complexity is always very high for this kind of problems. As you said this is a BFS way, so the time complexity equals to O(V+E) - same as DFS way. In this case V = E+1, and V equals to 1! + 2! + ... + n!. So the overall time complexity is something between O(n!) and O(n*n!).


  • 0
    W

    Good idea! I support the two point you said. my code is defferent from you .But the way of thinking is the same!


Log in to reply
 

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