LintCode 685 First Unique Number in Data Stream

思路

如果没限制遍历次数的话，可以第一遍遍历简单的先用hashmap记录次数，第二次遍历nums数组来寻找第一个unique的数字。如果只能遍历一遍的话就是用linkedlist+hashmap的做法。

时间复杂度O(n)
空间复杂度O(n)

代码

public class Solution {
    /*** @param nums: a continuous stream of numbers* @param number: a number* @return: returns the first unique number*/public int firstUniqueNumber(int[] nums, int number) {
    // Write your code hereMap<Integer, Integer> map = new HashMap<>();// countfor (int num : nums) {
    if (!map.containsKey(num)) {
    map.put(num, 1);} else {
    map.put(num, map.get(num) + 1);}if (num == number) {
    break;}}if (!map.containsKey(number)) {
    return -1;}// findfor (int num : nums) {
    if (map.get(num) == 1) {
    return num;}if (num == number) {
    break;}}return -1;}
}