【剑指Offer】字符流中第一个不重复的字符

Posted on | In ,

题目

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符“go”时，第一个只出现一次的字符是‘g’。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是‘l’。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private int[] occurrence = new int[256];
private int index = 0;

public void Insert(char ch) {
    index++;
    int current = (int) ch;

    if (occurrence[current] == 0)
        occurrence[current] = index;
    else if (occurrence[current] > 0)
        occurrence[current] = -1;
}

public char FirstAppearingOnce() {
    char result = '\0';
    int min = Integer.MAX_VALUE;

    for (int i = 0; i < 256; i++) {
        if (occurrence[i] > 0 && occurrence[i] < min) {
            result = (char) i;
            min = occurrence[i];
        }
    }

    if (result == '\0')
        result = '#';

    return result;
}