第一个只出现一次的字符

题目描述

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

思路：将每个字符作为数组下标，数组中记录出现的次数。

代码：

    int FirstNotRepeatingChar(string str) {
        map<char,int> mp;
        int len = str.size();
        if(len == 0) return -1;
        for(int i = 0; i < len;i++)
        {
            mp[str[i]]++;
        }
        for(int i = 0; i < len;i++)
        {
            if(mp[str[i]] == 1)
                return i;
        }
        return -1;
    }

 稍稍微微改进版的：减少了时间复杂度，第二次遍历只遍历256次即可。

    int FirstNotRepeatingChar(string str) {
        int arr[256] = {-1};
        memset(arr,-1,sizeof(arr));
        int len = str.size();
        if(len == 0) return -1;
        for(int i = 0; i < len;i++)
        {
            if(arr[str[i]]  == -1)
                arr[str[i]] = i;
            else 
                arr[str[i]] = -2;
        }
        int n  = len;
        for(int i = 0; i < 256;i++)
        {
            if(arr[i] != -1 && arr[i] != -2)
            {
                if(arr[i] < n)
                    n = arr[i];
            }
        }
        if(n == len)
            n = -1;
        return n;
    }

思路：申请256位的辅助数组，将数组置为-1，如果字符第一次出现置为字符位置，如果不是第一次置为-2，最后比较辅助数组中值不为-1和-2的，且下标最小的数。

int型数组存的值，可以代表多种不同的意义。