【剑指Offer】第一个只出现一次的字符

Posted on | In ,

题目

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

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int FirstNotRepeatingChar(String str) {
    if (str == null || str.length() == 0)
        return -1;

    Map<Character, Integer> map = new HashMap<>();

    for (int i = 0; i < str.length(); i++) {
        Character ch = str.charAt(i);

        if (map.containsKey(ch))
            map.put(ch, map.get(ch) + 1);
        else
            map.put(ch, 1);
    }

    for (int i = 0; i < str.length(); i++) {
        Character ch = str.charAt(i);

        if (map.get(ch) == 1)
            return i;
    }

    return -1;
}

相关题目

  1. 定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有字符。例如从第一个字符串“We are students. ”中删除在第二个字符串“aeiou”中出现过的字符得到的结果是“W r Stdnts. ”。为了解决这个问题，可以创建一个用数组实现的简单哈希表来存储第二个字符串。这样从头到尾扫描第一个字符串的每一个字符时，用O(1)时间就能判断出该字符是不是在第二个字符中。如果第一个字符串的长度是n，那么总的时间复杂度是O(n)。

  2. 定义一个函数，删除字符串中所有重复出现的字符。例如输入“google”，删除重复的字符之后的结果是“gole”。可以创建一个用布尔型数组实现的简单的哈希表。数组中的元素的意义是其下标看做ASCII码后对应的字母在字符串中是否已经出现。先把数组中所有的元素都设为false。以“google”为例，当扫描到第一个g时，g的ASCII码是103，那么把数组中下标为103的元素设为true。当扫描到第二个g时，发现数组中下标为103的元素的值是true，就知道g在前面已经出现了。也就是说，用O(1)时间就能判断出每个字符是否在前面已经出现过。如果字符串的长度是n，那么总的时间复杂度是O(n)。

  3. 在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词（Anagram）。例如silent与listen、evil与live等互为变位词。请完成一个函数，判断输入的两个字符串是不是互为变位词。可以创建一个用数组实现的简单哈希表，用来统计字符串中每个字符出现的次数。当扫描到第一个字符串中的每个字符时，为哈希表对应的项的值增加1.接下来扫描第二个字符串，扫描到每个字符时，为哈希表对应的项的值减去1.如果扫描完第二个字符串后，哈希表中所有的值都是0，那么这两个字符串就互为变位词。