算法练习(18) - 第一个唯一数字

题目

给一个连续的数据流,写一个函数返回终止数字到达时,终止数字前面出现的第一个唯一数字即只出现一次的函数（包括终止数字）,如果在终止数字前无唯一数字或者找不到这个终止数字, 返回 -1。

Input:
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirst
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]

Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5); // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2); // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3); // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

题解

import java.util.HashMap;
import java.util.LinkedList;

public class FirstUnique {

    LinkedList<Integer> linkedList = new LinkedList<>();
    LinkedList<Integer> temp = new LinkedList<>();
    HashMap<Integer,Integer> hashMap = new HashMap<>();

    private int showFirstUnique() {
        while (linkedList.peek() != null){
            Integer pop = linkedList.pop();
            if(hashMap.get(pop) < 2){
                return pop;
            }
            temp.offer(pop);
        }
        LinkedList<Integer> t = temp;
        temp = linkedList;
        linkedList = t;
        return -1;
    }

    public static void main(String[] args) {

        FirstUnique firstUnique = new FirstUnique();
        firstUnique.add(2);
        firstUnique.add(3);
        firstUnique.add(5);
        System.out.println(firstUnique.showFirstUnique());
        firstUnique.add(2);
        System.out.println(firstUnique.showFirstUnique());
    }

    private void add(int i) {
        if(hashMap.get(i) != null){
            hashMap.put(i,hashMap.get(i)+1);
        }else{
            hashMap.put(i,1);
        }
        linkedList.offer(i);
    }
}