JZ75 字元流中第一個不重覆的字元

題目

請實現一個函數用來找出字元流中第一個只出現一次的字元。例如，當從字元流中只讀出前兩個字元 "go" 時，第一個只出現一次的字元是 "g"。
當從該字元流中讀出前六個字元 “google" 時，第一個只出現一次的字元是"l"。

方法1 使用LinkedHashMap

思路

演算法實現

LinkedHashMap實現順序插入，不過查詢速度會比較慢

具體做法：
    step 1：用哈希表統計每個字元的次數，是全局變數。
    step 2：在Insert函數中對輸入的字元，然後統計出現次數。
    step 3：在FirstAppearingOnce函數遍歷該字元串，對於每個字元查找哈希表，返回第一個計數為1的字元，則返回#。

代碼

package mid.JZ75字元流中第一個不重覆的字元;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
    Map<Character,Integer> map = new LinkedHashMap<>();

    //Insert one char from stringstream
    public void Insert(char ch) {
        map.put(ch, map.getOrDefault(ch, 0) + 1);
    }

    //return the first appearence once char in current stringstream

    /**
     * LinkedHashMap實現順序插入，不過查詢速度會比較慢
     * 運行時間     165ms
     * 占用記憶體     15860KB
     * @return
     */
    public char FirstAppearingOnce() {
        for (Character character : map.keySet()) {
            if (map.get(character) == 1) {
                return character;
            }
        }
        return '#';
    }
}

方法2 哈希表+字元串（推薦使用）

思路

演算法實現

又是一個找到是否重覆的問題。我們還是可以用哈希表來記錄各個字元出現的次數，
根據這樣只要是字元串最前面且哈希表中次數為1的字元就是我們要找的。

具體做法：
    step 1：準備一個字元串來記錄輸入的字元流，用哈希表統計每個字元的次數，二者都是全局變數。
    step 2：在Insert函數中對輸入的字元，加到字元串最後，然後統計出現次數。
    step 3：在FirstAppearingOnce函數遍歷該字元串，對於每個字元查找哈希表，返回第一個計數為1的字元，
    如果遍歷完字元串以後都沒，則返回#。

代碼

package mid.JZ75字元流中第一個不重覆的字元;

import java.util.HashMap;
import java.util.Map;

public class Solution2 {
    StringBuilder sb = new StringBuilder();
    Map<Character,Integer> map = new HashMap<>();

    //Insert one char from stringstream
    public void Insert(char ch) {
        sb.append(ch);
        map.put(ch, map.getOrDefault(ch, 0) + 1);
    }

    //return the first appearence once char in current stringstream

    /**
     * 運行時間     13ms
     * 占用記憶體     9952KB
     * @return
     */
    public char FirstAppearingOnce() {
        for (int i = 0; i < sb.length(); i++) {
            if (map.get(sb.charAt(i)) == 1) {
                return sb.charAt(i);
            }
        }
        return '#';
    }
}

方法3 哈希表+字元串（推薦使用）

思路

演算法實現

除了使用字元串記錄字元流，還可以用隊列記錄字元流，每次插入的時候，只需要將第一次出現的字元加入到隊列中，然後正常計數。
查找第一個不重覆出現的字元的時候，從隊首開始查詢哈希表，
如果出現次數為1，則返回該字元，如果不為1，則從隊首將其彈出。

具體做法：
    step 1：準備一個隊列來記錄輸入的字元流，用哈希表統計每個字元的次數，二者都是全局變數。
    step 2：在Insert函數中對輸入的字元，加到隊列最後，然後統計出現次數。
    step 3：在FirstAppearingOnce函數中，不斷檢查隊首元素直到隊列為空，隊首出現次數為1次，就返回，
    隊首出現次數不為1就彈出。，則返回#。

代碼

package mid.JZ75字元流中第一個不重覆的字元;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution3 {
    Queue<Character> queue = new LinkedList<>();
    Map<Character,Integer> map = new HashMap<>();

    //Insert one char from stringstream
    public void Insert(char ch) {
        if (!map.containsKey(ch)) {
            queue.offer(ch);
        }
        map.put(ch, map.getOrDefault(ch, 0) + 1);
    }

    //return the first appearence once char in current stringstream

    /**
     * 運行時間     15ms
     * 占用記憶體     9972KB
     * @return
     */
    public char FirstAppearingOnce() {
        while(!queue.isEmpty()) {
            if (map.get(queue.peek()) == 1) {
                return queue.peek();
            } else {
                queue.poll();
            }
        }
        return '#';
    }
}