34.第一个只出现一次的字符.md

34.第一个只出现一次的字符

题目描述

• 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。

 

解题思路

下面的思路来自《剑指offer》。

• 思路一，笨办法。遍历每个字符，每个字符都和所有的字符对比。

• 思路二，哈希表（字典，map）。第一次遍历的时候统计每个字符出现的次数，第二次遍历的时候查看字符串中每个字符出现的次数是否等于1。

  如果不能用标准库中的map的话，可以用数组来解决，因为题目的字符串中只有字母，因此大小写字母加起来总共48个字符，但是ASCII表中大小写字符不是连起来的，中间还有一些其他字符，因此从大写的A（65）到小写的z（122）总共58个字符，创建一个大小为58个字符的数组即可，用ASCII码-65作为下标。或者干脆直接创建一个大小为256的数组，反正ASCII表总共也就才256个字符。

 

代码

• 思路二，哈希表（字典，map）。用数组替代哈希表。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unsigned short int freq[58]={0}; // 用于统计频率
        int length = str.size();
        for(int i=0;i<length;i++){
            freq[str[i]-65]++;
        }
        for(int i=0;i<length;i++){
            if(freq[str[i]-65]==1) return i;
        }
        return -1;
    }
};