剑指offer——第一个只出现一次的字符---AI那点小事

概述

题目描述 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1.

思路

当字符串为空返回-1，初始化计数哈希表cnt来记录每个字符的出现的次数， 位置哈希表index来记录每个字符第一次出现的位置，集合s存放不重复元素。 遍历整个字符串，首先对每个字符str[i]的出现次数加1，若index中没有str[i]且cnt[str[i]]为1，那么把str[i]放入s，且赋值index[str[i]] = i。否则从s和index中删除str[i]。如出现整个字符串只有一个不字符，返回-1，否则遍历s集合，找到第一个只出现一次的字符的下标。

C++ AC代码#include <iostream> #include <map> #include <set> using namespace std; class Solution { public: int FirstNotRepeatingChar(string str) { if(str.length() == 0){ return -1; } map<char,int> cnt; // 用于字符计数 map<char,int> index; // 用于记录字符的首次出现位置 set<char> s; // 记录只出现一次的字符 bool flag = false; for(int i = 0 ; i < str.length() ; i++){ cnt[str[i]]++; if(index.find(cnt[i]) == index.end() && cnt[str[i]] == 1){ index[str[i]] = i; s.insert(str[i]); }else{ index.erase(str[i]); s.erase(str[i]); } if(cnt[str[i]] == str.length()){ flag = true; //判断字符串有重复1个字符组成 break; } } if(flag == true){ return -1; } int min = 10000; for(set<char>::iterator i = s.begin() ; i != s.end() ; i++){ if(cnt[*i] == 1 && index[*i] < min ){ min = index[*i]; } } return min; } };

---来自腾讯云社区的---AI那点小事