A 7ms Customized Node Solution without visited array


  • 0
    L

    The 7ms solution avoids the full scan of array in each recursion function. And the logic is the most straightforward.

    public class Solution {
        class Node{
            public int num;
            public Node next;
            public Node(int num){
                this.num = num;
            }
        }
        public List<List<Integer>> permuteUnique(int[] nums) {
            Node head = new Node(-1);
            Node cur = head;
            Arrays.sort(nums);
            for(int num: nums){
                cur.next = new Node(num);
                cur = cur.next;
            }
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            dfs(res, head, head);
            return res;
        }
        
        private void dfs(List<List<Integer>> res, Node head, Node curHead){
            if(curHead.next == null){
                List<Integer> list = new ArrayList();
                Node cur = head;
                while(cur.next != null){
                    cur = cur.next;
                    list.add(cur.num);
                }
                res.add(list);
                return;
            }
            dfs(res, head, curHead.next);
            Node cur = curHead.next;
            while(cur.next != null){
                if(cur.num != cur.next.num){
                    Node tmp = cur.next;
                    cur.next = tmp.next;
                    tmp.next = curHead.next;
                    curHead.next = tmp;
                    dfs(res,head, curHead.next);
                    curHead.next = tmp.next;
                    tmp.next = cur.next;
                    cur.next = tmp;
                }
                cur = cur.next;
            }
        }
    }
    

Log in to reply
 

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