字符只能一個接著一個從字符流中讀出來?？梢远x一個數(shù)據(jù)容器來保存字符在字符流中的位置。當(dāng)一個字符第一次從字符流中讀出來時，把它在字符流中的位置保存到數(shù)據(jù)容器里。當(dāng)這個字符再次從字符流中被讀出來時，那么它就不是只出現(xiàn)一次的字符，也就可以被忽略了。這時把它在數(shù)據(jù)容器里保存的值更新成一個特殊的值（比如負(fù)值）。

為了盡可能高校地解決這個問題，需要在 O(1)時間內(nèi)往容器里插入一個字符，以及更新一個字符對應(yīng)的值。這個容器可以用哈希表來實現(xiàn)。用字符的 ASCII 碼作為哈希表的鍵值，而把字符對應(yīng)的位置作為哈希表的值。

代碼實現(xiàn)

public class Test55 {
    /**
     * 題目：請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符。
     */
    private static class CharStatistics {
        // 出現(xiàn)一次的標(biāo)識
        private int index = 0;
        private int[] occurrence = new int[256];
        public CharStatistics() {
            for (int i = 0; i < occurrence.length; i++) {
                occurrence[i] = -1;
            }
        }
        private void insert(char ch) {
            if (ch > 255) {
                throw new IllegalArgumentException( ch + "must be a ASCII char");
            }
            // 只出現(xiàn)一次
            if (occurrence[ch] == -1) {
                occurrence[ch] = index;
            } else {
                // 出現(xiàn)了兩次
                occurrence[ch] = -2;
            }
            index++;
        }
        public char firstAppearingOnce(String data) {
            if (data == null) {
                throw new IllegalArgumentException(data);
            }
            for (int i = 0; i < data.length(); i++) {
                insert(data.charAt(i));
            }
            char ch = '\0';
            // 用于記錄最小的索引，對應(yīng)的就是第一個不重復(fù)的數(shù)字
            int minIndex = Integer.MAX_VALUE;
            for (int i = 0; i < occurrence.length; i++) {
                if (occurrence[i] >= 0 && occurrence[i] < minIndex) {
                    ch = (char) i;
                    minIndex = occurrence[i];
                }
            }
            return ch;
        }
    }
    public static void main(String[] args) {
        System.out.println(new CharStatistics().firstAppearingOnce("")); // '\0'
        System.out.println(new CharStatistics().firstAppearingOnce("g")); // 'g'
        System.out.println(new CharStatistics().firstAppearingOnce("go")); // 'g'
        System.out.println(new CharStatistics().firstAppearingOnce("goo")); // 'g'
        System.out.println(new CharStatistics().firstAppearingOnce("goog")); // '\0'
        System.out.println(new CharStatistics().firstAppearingOnce("googl")); // l
        System.out.println(new CharStatistics().firstAppearingOnce("google")); // l
    }
}

運(yùn)行結(jié)果

http://wiki.jikexueyuan.com/project/for-offer/images/73.png" alt="" />

下一篇：打印 1 到最大的 n 位數(shù)