1429. First Unique Number

 一刷 06/2022

Version #1 Doubly linked list + HashMap

Similar to using LinkedHashSet

Time Constructor O(N), Add O(1), FirstUnique O(1)

Space O(N)

Runtime: 259 ms, faster than 22.42% of Java online submissions for First Unique Number.

Memory Usage: 167 MB, less than 24.63% of Java online submissions for First Unique Number.

class FirstUnique {

    ListNode dummy;

    ListNode tail;

    Set<Integer> duplicates;

    Map<Integer, ListNode> nodes;

    

    class ListNode {

        public ListNode prev, next;

        public int val;

        public ListNode(int val) {

            this.val = val;

        }

     }

    public FirstUnique(int[] nums) {

        dummy = new ListNode(-1);

        tail = dummy;

        duplicates = new HashSet<>();

        nodes = new HashMap<>();

        for (int num : nums) {

            add(num);

        }

    }

    

    public int showFirstUnique() {

        if (dummy.next == null) {

            return -1;

        }

        return dummy.next.val;

    }

    

    public void add(int value) {

        // If value is first time seen, add it to the nodes hashmap and add to the end of the list

        // If value is in the duplicates set, do nothing

        // If currently is unique, put to the duplicates hashset, remove from the linkedlist and nodes map

        if (duplicates.contains(value)) {

            return;

        }

        if (nodes.containsKey(value)) {

            ListNode node = nodes.get(value);

            duplicates.add(value);

            nodes.remove(value);

            node.prev.next = node.next;

            if (node.next != null) {

                node.next.prev = node.prev;

            } else {

                tail = tail.prev;

            }

            return;

        }

        ListNode node = new ListNode(value);

        tail.next = node;

        node.prev = tail;

        tail = tail.next;

        nodes.put(value, node);

    }

}

/**

 * Your FirstUnique object will be instantiated and called as such:

 * FirstUnique obj = new FirstUnique(nums);

 * int param_1 = obj.showFirstUnique();

 * obj.add(value);

 */