題目描述

請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符返弹。例如耳奕，當(dāng)從字符流中只讀出前兩個字符"go"時心包，第一個只出現(xiàn)一次的字符是"g"身辨。當(dāng)從該字符流中讀出前六個字符“google"時概龄，第一個只出現(xiàn)一次的字符是"l"还惠。

輸出描述:

如果當(dāng)前字符流沒有存在出現(xiàn)一次的字符，返回#字符私杜。

解法一：

我們分析一下這道題目蚕键，它要求每輸入一個字符，都可以獲得當(dāng)前全部字符中只出現(xiàn)一次的字符衰粹，這說明輸入的這個字符與全局信息密切相關(guān)锣光，即輸入的這個字符可以獲得全局信息。這說明既要記錄全局信息铝耻，全局信息記錄方式又要與字符相關(guān)誊爹，很明顯我們可以記錄下每個字符出現(xiàn)的次數(shù)，這樣加入新字符時我們便可以對全局信息進(jìn)行更新。哈希表可以滿足我們的要求频丘。
但僅僅知道全部字符的出現(xiàn)次數(shù)還是不夠的箍铭，我們還需要知道哪個字符才是第一個次數(shù)為1的字符。假如當(dāng)輸入的新字符使原來的第一個次數(shù)為1的字符次數(shù)變?yōu)榱?椎镣，我們需要知道第二個次數(shù)為1的字符诈火，以此類推第三個第四個直到最后一個我們都需要直到。而普通哈希表是無序的状答，并不能完成這個任務(wù)冷守，但LinkedHashMap可以。

public class Solution {
    Map<Object, Integer> map = new LinkedHashMap<Object, Integer>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(map.containsKey(ch)) {
            map.put(ch, map.get(ch) + 1);
        }
        else {
            map.put(ch, 1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(Entry<Object, Integer> entry : map.entrySet()) {
            if(entry.getValue() == 1) {
                return (char) entry.getKey();
            }
        }
        return '#';
    }
}

解法二：

可以實現(xiàn)自己的哈希表惊科，由于LinkedHashMap包含了出現(xiàn)次序拍摇、字符、出現(xiàn)次數(shù)三種信息馆截，但由于自己的哈希表使用的是數(shù)組充活，只有下標(biāo)與值，所以要想辦法只用兩個變量記錄這三個值蜡娶，可以使用數(shù)組值同時記錄出現(xiàn)次序與出現(xiàn)次數(shù)混卵，若次數(shù)等于0則數(shù)組值為-1，次數(shù)等于1數(shù)組值為出現(xiàn)位置窖张，次數(shù)大于1數(shù)組值為-2幕随。也就是通過合法與非法值來標(biāo)記出現(xiàn)次數(shù)信息。ASCII碼表只有128個字符宿接，可以使用ASCII碼作為數(shù)組的下標(biāo)赘淮，數(shù)組的值記錄對應(yīng)字符第一次出現(xiàn)的位置，若字符不止出現(xiàn)了一次睦霎，則位置記錄為-2梢卸，若還沒有出現(xiàn)過，記錄位置為-1副女。

public class Solution {
    int[] myHashMap = new int[128];
    int index = 0;
    Solution() {
        for(int i = 0; i < myHashMap.length; i++) {
            myHashMap[i] = -1;
        }
    }
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(myHashMap[(int)ch] == -1) {
            myHashMap[(int)ch] = index;
        }
        else if(myHashMap[(int)ch] >= 0) {
            myHashMap[(int)ch] = -2;
        }
        index++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        int min = Integer.MAX_VALUE;
        char ch = '#';
        for(int i = 0; i < myHashMap.length; i++) {
            if(myHashMap[i] < min && myHashMap[i] >= 0) {
                ch = (char)i;
                min = myHashMap[i];
            }
        }
        return ch;
    }
}

相似題目：第一個只出現(xiàn)一次的字符