960. First Unique Number in Data

Description

We need to implement a data structure named DataStream. There are two methods required to be implemented:

void add(number) // add a new number

int firstUnique() // return first unique number

You can assume that there must be at least one unique number in the stream when calling the firstUnique.

Example

Example 1:

Input:

add(1)

add(2)

firstUnique()

add(1)

firstUnique()

Output:

[1,2]

Example 2:

Input:

add(1)

add(2)

add(3)

add(4)

add(5)

firstUnique()

add(1)

firstUnique()

add(2)

firstUnique()

add(3)

firstUnique()

add(4)

firstUnique()

add(5)

add(6)

firstUnique()

Output:

[1,2,3,4,5,6]

思路：

使用类似 LRU Cache 的做法来做。

hash 的 key 为 num，value 为对应的 linkedlist 上的 previous node

当一个数第一次被加进来的时候连在tail上，第二次被加进来的时候，存储在duplicate中，并且从Linkedlist中删除，第三次及以后就加不进来，这样linked list里永远存储的是不重复的数。

代码：