LeetCode 387. first-unique-character-in-a-string    原题链接    简单

作者： 作者的头像   阿英Tori ,  2019-04-23 11:34:57 ,  所有人可见 ,  阅读 1002

0


题目描述

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

样例

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

算法1

(扫描) $O(n)$

用一个26长度的数组统计每个字母出现的次数
依次扫描字符，看出现的次数是否为1

时间复杂度分析：O(n)

Java 代码

class Solution {
    public int firstUniqChar(String s) {
        int[] arr = new int[26];
        for (int i=0;i<s.length();i++) {
            arr[s.charAt(i)-'a']++;
        }
        for (int i=0;i<s.length();i++) {
            if (arr[s.charAt(i)-'a']==1)
                return i;
        }
        return -1;
    }
}

1 评论

用户头像
T-SHLoRk   2019-08-04 01:11         踩      回复

可以将每个字符第一次出现的位置存下来，这样第二次只需要遍历26个字母而不是整个字符串了。如果字符串比较长的话，可以使用这种方法。

  int firstUniqChar(string s) {
        vector<vector<int>> f(26,{0,-1});
        int n = s.length(),res = n;
        for(int i = 0 ; i < n ; i ++)
        {
            f[s[i] - 'a'][0] ++;
            if(f[s[i]- 'a'][1] == -1)
                f[s[i]- 'a'][1] = i;
        }
        for(int i = 0 ; i < 26 ; i ++)
        {
            if(f[i][0] == 1)
                res = min(res,f[i][1]);
        }
        return res == n ? -1 : res;
    }