09.字符流中第一个不重复的字符.md

目录介绍

• 01.题目要求
• 02.问题分析
• 03.实例代码

好消息

• 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
• 链接地址：https://github.com/yangchong211/YCBlogs
• 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.题目要求

• 问题如下所示：
  • 请实现一个函数用来找出字符流中第一个只出现一次的字符。
• 示例 :
  • 例如，当从字符流中只读出前两个字符“Go”时，第一个只出现一次的字符是‘g’。当从该字符流中读出前六个字符“google”时，第一个只出现1次的字符是”l”。

02.问题分析

• 字符只能一个接着一个从字符流中读出来。可以定义一个数据容器来保存字符在字符流中的位置。当一个字符第一次从字符流中读出来时，把它在字符流中的位置保存到数据容器里。当这个字符再次从字符流中被读出来时，那么它就不是只出现一次的字符，也就可以被忽略了。这时把它在数据容器里保存的值更新成一个特殊的值（比如负值）。
• 为了尽可能高校地解决这个问题，需要在O(1)时间内往容器里插入一个字符，以及更新一个字符对应的值。这个容器可以用哈希表来实现。用字符的ASCII码作为哈希表的键值，而把字符对应的位置作为哈希表的值。

03.实例代码

• 如下所示

public class Test {
    /**
     * 题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。
     */
    private static class CharStatistics {
        // 出现一次的标识
        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");
            }

            // 只出现一次
            if (occurrence[ch] == -1) {
                occurrence[ch] = index;
            } else {
                // 出现了两次
                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';
            // 用于记录最小的索引，对应的就是第一个不重复的数字
            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;
        }
    }
}

其他内容

01.关于博客汇总链接

• 1.技术博客汇总
• 2.开源项目汇总
• 3.生活博客汇总
• 4.喜马拉雅音频汇总
• 5.其他汇总

02.关于我的博客

• 我的个人站点：
• github：https://github.com/yangchong211
• 知乎：https://www.zhihu.com/people/yczbj/activities
• 简书：http://www.jianshu.com/u/b7b2c6ed9284
• csdn：http://my.csdn.net/m0_37700275
• 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
• 开源中国：https://my.oschina.net/zbj1618/blog
• 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
• 邮箱：yangchong211@163.com
• 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
• segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
• 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e