[34] 第一个只出现一次的字符(简单)
[34] 第一个只出现一次的字符(简单)

题目描述

在一个字符串(0 <= 字符串长度 <= 10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,如果没有则返回 -1(需要区分大小写)。
0 开始计数。
输入:"google"
返回值:4

解题思路

哈希表

用哈希表存储每个字符和其出现的次数,最后找出出现次数为 1 的即可。这里降低内存消耗,使用数组来存储,字符的 ASCAII 码作为指定下标,出现次数为元素值。
/**
 * 哈希表
 *
 * T(2n) S(n)
 */
public int FirstNotRepeatingChar(String str) {
		// ASCAII 码有 128 个
    int[] count = new int[128];
    for (int i = 0; i < str.length(); i++) {
        count[str.charAt(i)]++;
    }
    System.out.println(Arrays.toString(count));
    for (int i = 0; i < str.length(); i++) {
        if (count[str.charAt(i)] == 1) {
            return i;
        }
    }
    return -1;
}