面试题35:第一个只出现一次的字符

简介:
题目:在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”,则输出‘b’。

方法1:

看到这个题目,最直观的想法就是就是遍历法,也就是从头开始取字符串中的一个字符,将其与其后的所有字符比较,如果有相同的字符,那么就证明它不是只出现一次的字符。当第一次出现遍历完其后字符并且没有重复时,表明这个字符就是“第一个只出现一次的字符”。如果字符串有n个字符,每个字符可能与后面的O(n)个字符相比较,因此这种思路的时间复杂度是O(n2)。

方法2:

题目中要求第一个只出现一次的字符,那么就跟字符出现的次数有关。我们考虑如何统计字符出现的次数,然后找出第一个次数为1的那个字符。这里我们需要一个数据容器来保存字符出现次数,并且能够通过字符找出其相对应的次数。哈希表就是一种常用用的容器。

我们可以定义哈希表的键值(Key)是字符的ASCII值,而值(Value)是该字符出现的次数。同时我们需要扫描两次字符串,第一次扫描字符串时,每扫描到一个字符就在哈希表的对应项中把次数加1。接下来第二次扫描的时候,没扫描到一个字符就能在哈希表中得到该字符出现的次数。找出第一个Value为1的那个key就是我们需要找到那个字符。

方法1和方法2的代码实现

View Code

字符(char)是一个长度为8bit的数据类型,因此总共最多能够表示256种字符。所以在前面的代码示例中我们直接创建了一个长度为256的整型数组,每个字符根据其ASCII值作为数组的下标对应数组的一个数字,而数组中存储的是每个字符出现的次数。这样我们就创建了一个大小为256,以字符ASCII吗为键值的哈希表。

但是假如我们的字符串长度小于256,那么我们可以通过创建一个字符串长度的整型数组来存放键值,键值是ASCII%len。代码实现如下:

View Code

上述思想错误,因为ASCII%len结果相等,但是ASCII可能不相等。比如字符串为“abacdeffk”,那么第一个只出现一次的字符不是b,而是c。这是因为b跟k对len求hash值结果相同。

 

 本文转自xwdreamer博客园博客,原文链接:http://www.cnblogs.com/xwdreamer/archive/2012/09/26/2703739.html,如需转载请自行联系原作者

目录
相关文章
|
2月前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
9月前
|
算法 程序员
【Leetcode】NC31 第一个只出现一次的字符(牛客网)、面试题 01.01. 判定字符是否唯一
题目描述: 描述 在一个长为n字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)
48 0
|
2月前
|
算法
面试题 01.01:判定字符是否唯一
面试题 01.01:判定字符是否唯一
24 0
|
2月前
剑指Offer LeetCode 面试题50. 第一个只出现一次的字符
剑指Offer LeetCode 面试题50. 第一个只出现一次的字符
26 0
|
11月前
|
Java 数据处理
Java IO(File、字节输入输出流、字符输入输出流、打印流)附带相关面试题
1.File类,2.字节输入输出流(InputStream Outputstream),3.Writer与Reader字符输入输出流,4.打印流
69 0
|
编译器 C语言 C++
C语言面试题 - 字符空间操作类
C语言面试题 - 字符空间操作类
65 0
|
算法 索引
【Day15】算法刷题(解题思路+详细注释)[面试题 17.09. 第 k 个数 ][424. 替换后的最长重复字符 ][438. 找到字符串中所有字母异位词 ]
了解[面试题 17.09. 第 k 个数 ][424. 替换后的最长重复字符 ][438. 找到字符串中所有字母异位词 ]。
143 0
【Day15】算法刷题(解题思路+详细注释)[面试题 17.09. 第 k 个数 ][424. 替换后的最长重复字符 ][438. 找到字符串中所有字母异位词 ]
|
存储 算法
面试高频算法题---无重复字符的最长子串
给定一个字符串s,请你找出其中不含有重复字符的最长子串长度
面试高频算法题---无重复字符的最长子串
|
存储 关系型数据库 MySQL
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(3)
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(3)
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(3)
|
存储 关系型数据库 MySQL
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(2)
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(2)
580 0
面试官:MySQL 中的 varchar 最多能存储多少个字符?大部分人都会答错。。。(2)