leetcode——[387]First Unique Character in a String字符串中的第一个唯一字符

题目

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

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

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

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.

解题方法

HashMap

将字符串转化为字符数组，先用HashMap保存每个字符出现的次数，然后在遍历一次字符数组，将value为1的字符索引输出。这段代码时间复杂度为O(n)，跑了79ms，只超过了31.38%的java提交。

// Method_01  79ms  31.38%
class Solution {
    public int firstUniqChar(String s) {
        char[] chars = s.toCharArray();
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (char ch :
                chars) {
            hashMap.put(ch, hashMap.get(ch) == null ? 1 : hashMap.get(ch) + 1);
        }
        for (int i = 0; i < chars.length; i++) {
            if (hashMap.get(chars[i]) == 1) {
                return i;
            }
        }
        return -1;
    }
}

嵌套循环

通过两次循环，逐个判断字符是否重复出现。这段代码时间复杂度为O(n^2)，跑了48ms，超过了48.97%的java提交。

// Method_02  48ms  48.97%
class Solution {
    public int firstUniqChar(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            boolean unique = true;
            for (int j = 0; j < chars.length; j++) {
                if (chars[i] == chars[j] && i != j) {
                    unique = false;
                    break;
                }
            }
            if (unique) {
                return i;
            }
        }
        return -1;
    }
}

判断所有字母是否重复

循环判断26个字母中每一个字母是否重复，对每一个字母，找到第一次出现和最后一次出现的索引，索引不相等则说明重复出现，相等则说明只出现了一次，用一个变量保存索引最小值，即为字符串中第一个唯一字符。这段代码时间复杂度为O(n)，跑了7ms，超过了98.63%的java提交。

// Method_03  7ms  98.63%
class Solution {
    public int firstUniqChar(String s) {
        int start;
        int end;
        int result = s.length();
        for(char ch='a';ch<='z';ch++) {
            start = s.indexOf(ch);
            end = s.lastIndexOf(ch);
            if(start == end && start != -1) {
                result = Math.min(result,start);
            }
        }
        if(result == s.length()) {
            return -1;
        }
        return result;
    }
}