剑指offer | 字符串中第一个不重复的字符

2019-08-02  本文已影响0人  icebreakeros

字符串中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符

示例
输入:google
输出:l

分析:
使用哈希表实现,用字符的ASCII码作为哈希表的键值,而把字符对应的位置作为哈希表的值

public class CharStatistics {

    private int index = 0;
    private int[] occurrence = new int[256];

    public CharStatistics() {
        for (int i = 0; i < 256; i++) {
            occurrence[i] = -1;
        }
    }

    public void insert(char ch) {
        if (occurrence[ch] == -1) {
            occurrence[ch] = index;
        } else if (occurrence[ch] >= 0) {
            occurrence[ch] = -2;
        }
        index++;
    }

    public char firstAppearingOnce() {
        char result = '\0';
        int index = Integer.MAX_VALUE;
        for (int i = 0; i < 256; i++) {
            if (occurrence[i] >= 0 && occurrence[i] < index) {
                result = (char) i;
                index = occurrence[i];
            }
        }
        return result;
    }
}
上一篇下一篇

猜你喜欢

热点阅读