[剑指Offer]-第一个只出现一次的字符

题目描述

在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出’b’。

解题思路

为了解决这个问题，我们可以定义一个哈希表（外部空间），其键值（Key）是字符，而值（Value）是该字符出现的次数。

同时我们还需要从头开始扫描字符串两次： （1）第一次扫描字符串时，每扫描到一个字符就在哈希表的对应项中把次数加1。（时间效率O(n)） （2）第二次扫描时，每扫描到一个字符就能从哈希表中得到该字符出现的次数。

这样第一个只出现一次的字符就是符合要求的输出。（时间效率O(n)）

算法图解

参考代码：

package offer; /** * 第一个只出现一次的字符 */ public class Offer50 { public static void main(String[] args) { String s = "abaccdeff"; System.out.println(FirstNotRepeatingChar(s)); } /** * 1. 暴力法 不写了 O（n^2） * 2. hash O(1) O(n) * * @param str * @return */ public static char FirstNotRepeatingChar(String str) { if (str == " ") { return ' '; } char[] array = str.toCharArray(); int size = 256; // 借助数组来模拟哈希表，只用1K的空间消耗 int[] hastTable = new int[size]; // 初始化数组 for (int i = 0; i < size; i++) { hastTable[i] = 0; } for (int i = 0; i < array.length; i++) { hastTable[array[i]]++; } for (int i = 0; i < array.length; i++) { if (hastTable[array[i]] == 1) { return array[i]; } } return ' '; } }

---

附录

该题源码在我的 ?Github 上面！