一、题目

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事项:您可以假定该字符串只包含小写字母。

二、解决方法

方法一、我的笨方法

首先将字符串转换为字符数组,然后通过两个for循环遍历查找解决。
代码如下(通过)

int firstUniqChar(char* s) {
    int len = strlen(s);
    char* str = (char*)malloc(sizeof(char) * (len + 1));
    for (int i = 0; i < len; i++)
    {
        str[i] = *s;
        s++;
    }
    
    int cnt;
    int pos = -1;
    for (int i = 0; i < len; i++)
    {
        cnt = 0;
        for (int j = 0; j <= len - 1; j++)
        {
            if (i == j)
                j++;
            if (str[i] == str[j])
            {
                cnt++;
                break;
            }                
        }
        if (cnt == 0)
        {
            pos = i;
            break;
        }               
    }
    if (pos == -1)
        return -1;
    else
        return pos;
}

之间遇到的问题:AddressSanitizer: heap- buffer- overflow……如下图所示。

原因:leetcode使用AddressSanitizer检查内存是否存在非法访问。报此错,主要是访问了非法内容。
解决办法:排查代码,发现数组访问越越,导致此错,将申请的数组空间加大(这里只加1),问题解决。


方法二:线性时间复杂度解法(最优解法)

这道题最优的解法就是线性复杂度了,为了保证每个元素是唯一的,至少得把每个字符都遍历一遍。

算法的思路就是遍历一遍字符串,然后把字符串中每个字符出现的次数保存在一个散列表中。这个过程的时间复杂度为 O(N)O(N),其中 N 为字符串的长度。

接下来需要再遍历一次字符串,这一次利用散列表来检查遍历的每个字符是不是唯一的。如果当前字符唯一,直接返回当前下标就可以了。第二次遍历的时间复杂度也是 O(N)O(N)

伪hash实现代码如下

int firstUniqChar(char* s)
{   
    int mark[26]; // 标记数组
    memset(mark, 0, sizeof(mark));
    int length = strlen(s);
    for (int i = 0; i < length; i++)
        mark[s[i] - 'a']++; // 纪录每个字母个数
    int pos = -1;
    for (int i = 0; i < length; i++)
    {
        if (mark[s[i] - 'a'] == 1)
        {
            pos = i;
            break;
        }
    }
    return pos;
}