http://www.lintcode.com/tag/data-stream/

lt960. First Unique Number in a Stream II

每个操作都是O(1)

public class DataStream {
    class ListNode{
        int value;
        ListNode next;
        ListNode(int value){
            this.value = value;
        }
    }
    Map<Integer, ListNode> map = new HashMap<>();
    Set<Integer> set = new HashSet<>();
    ListNode dummy, tail;
    public DataStream(){
        // do intialization if necessary
        dummy = new ListNode(0);
        tail = dummy;
    }
    /**
     * @param num: next number in stream
     * @return: nothing
     */
    public void add(int num) {
        // write your code here
        if(set.contains(num)){
            if(map.containsKey(num)){
                ListNode pre = map.get(num);
                if(pre.next==tail){
                    tail = pre;
                }else{
                    map.put(pre.next.next.value, pre);
                    pre.next = pre.next.next;
                }
                map.remove(num);
            }
        }else{
            ListNode newNode = new ListNode(num);
            tail.next = newNode;
            map.put(num, tail);
            tail = newNode;
            set.add(num);
        }
    }

    /**
     * @return: the first unique number in stream
     */
    public int firstUnique() {
        // write your code here
        return dummy.next.value;
    }
}