剑指offer——第一个只出现一次的字符

AI那点小事

发布于 2020-04-18 00:49:54

4060

发布于 2020-04-18 00:49:54

文章被收录于专栏：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;
        }
};