求字符串中第一个只出现一次的字符

问题描述:给定一个字符串,假设字符串中只包含字母和数字,求出这个字符串中第一个只出现一次的字符。

分析:这个题目想要做出来还是比较简单的,关键是如何用高效的方法求解。这里我提供两种方法:

         解法一:蛮力法。具体思想为,从第一位开始,拿每一位和后面的每一位进行比较,如果没有出现,则直接输出这个字符。

                    如果出现,则从第二位开始,再和后面的每一位进行比较,依次类推。

                    算法的时间复杂度为O(n^2).

         解法二:哈希法。采用两次扫描即可实现。需要提前构建一个哈希表,把字符当成key值,把出现的次数当成value值,并初始化。

                    第一次扫描,统计出现的每个字符的次数,存到哈希表中;

                    第二次扫描,从字符串第一位开始,查看对应的value是否为1,如果为1,直接返回该字符,算法结束,否则,接着扫描。

                    算法的时间复杂度为O(n).空间复杂度为O(1).这种方法属于典型的空间换时间。

        由于算法比较简单,我就不再写具体的代码了,读者可以自行验证。

原文地址:https://www.cnblogs.com/guozhenqiang/p/5483609.html