题目描述

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

解法一

思路

想要找到第一个不重复的字符,那首先要定义出“不重复的字符”,而想要判断一个字符是不是“不重复的字符”,那首先遍历一遍字符串就是必须的了。在遍历字符串时,我们记录下每个字符的出现次数,而后再次遍历字符串,当遇到第一个出现次数为1(即此字符在字符串中仅出现一次)时,就可以返回了。

通常来说,在记录字符出现次数时应该用Map结构(key为字符,value为出现次数),但在这里我们应该更倾向于使用数组结构,因为字符只可能是小写字母,使用长为26的数组就好了(因为数组较Map来说速度更快)。

Python

class Solution:
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        counts = [0] * 26
        for item in s:
            counts[ord(item) - ord('a')] += 1
        for (index, item) in enumerate(s):
            if counts[ord(item) - ord('a')] == 1:
                return index
        return -1

Java

public class Solution {
    public int firstUniqChar(String s) {
        int[] counts = new int[26];
        for (char item : s.toCharArray()) {
            counts[item - 'a']++;
        }
        int index = 0;
        for (char item : s.toCharArray()) {
            if (counts[item - 'a'] == 1) {
                return index;
            }
            index++;
        }
        return -1;
    }
}

C++

class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> counts(26, 0);
        for (auto item : s) {
            counts[item - 'a']++;
        }
        for (int i = 0; i < s.size(); i++) {
            if (counts[s[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
};