LC: First Unique Number - spiralgo/algorithms GitHub Wiki

First Unique Number

The Essence:

Let's say that there are two sets of numbers, ones that are unique and ones that are all the numbers added. Trying to add an element to the set of all numbers when it's already present in that set would remove it from the set of unique. Noticing this, simply keeping the first unique number as primitive data is not enough. A more advanced data structure needs to be used to support yielding the next unique number after the first has been removed from the set of uniques.

Details:

The procedure described above can literally be implemented using sets, namely linked sets. When returning the unique value, the elements from the set need to be returned in order that they are added. Java's LinkedHashSet data structure supports this operation.

Beyond this the list of unique numbers can be represented using a linked list. Their presence can checked using a hash table, which also points out to the nodes. Adding when a node is present in the hash table would have the node removed from the linked list.