文章482
标签257
分类63

算法:字符流中第一个不重复的字符


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

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

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

例如,当从字符流中只读出前两个字符”go”时,第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时,第一个只出现一次的字符是”l”。

输出描述:

如果当前字符流没有存在出现一次的字符,返回#字符。


分析

在HashMap中记录每个字符出现的index, 重复时将值设为-1;

在取得第一个不重复的字符时, 遍历map寻找index最小并且不为-1的即可


代码

public class Solution {
    int[] count = new int[256];

    int index = 1;

    public void Insert(char ch) {
        if (count[ch] == 0) {
            count[ch] = index++;
        } else {
            count[ch] = -1;
        }
    }

    public char FirstAppearingOnce() {
        int temp = Integer.MAX_VALUE;
        char ch = '#';
        for (int i = 0; i < 256; i++) {
            if (count[i] != 0 && count[i] != -1 && count[i] < temp) {
                temp = count[i];
                ch = (char) i;
            }
        }
        return ch;
    }
}

本文作者:Jasonkay
本文链接:https://jasonkayzk.github.io/1996/07/27/算法-字符流中第一个不重复的字符/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可