LeetCode 387: 字元串中的第一個唯一字元 First Unique Character in a String

題目：

給定一個字元串，找到它的第一個不重複的字元，并傳回它的索引。如果不存在，則傳回 -1。

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

案例:

s = "leetcode"
傳回 0.

s = "loveleetcode",
傳回 2.           

注意事項：您可以假定該字元串隻包含小寫字母。

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

解題思路：

​ 很簡單的題，無非就是對字元串的字母進行頻率統計，找到出現頻率為1 的字母索引。

​ 借助哈希映射兩次周遊完成。第一次周遊進行字母頻率統計，Hash Map 的Key 為字母，Value 為出現頻率。第二次周遊找到頻率為 1 的字母索引傳回即可。

​ 不同于單詞頻率統計，字母一共隻有 26 個，是以可以直接利用 ASii 碼表裡小寫字母數值從 97～122，直接用 int 型數組映射。建立映射：索引為 小寫字母的 ASii 碼值，存儲值為出現頻率。

哈希映射解題：

Java：

class Solution {
    public int firstUniqChar(String s) {
        char[] chars = s.toCharArray();//轉成 Char 數組
        Map<Character, Integer> map = new HashMap<>();
        for (Character c: chars) map.put(c, map.getOrDefault(c, 0) + 1);//頻率統計
        for (int i = 0; i < chars.length; i++) {
            if(map.get(chars[i])==1) return i;//找到詞頻為1的字母(隻出現一次)傳回其索引
        }
        return -1;
    }
}           

Python：

class Solution:
    def firstUniqChar(self, s):
        count = collections.Counter(s)# 該函數就是Python基礎庫裡詞頻統計的內建函數
        index = 0
        for ch in s:
            if count[ch] == 1:
                return index
            else:
                index += 1       
        return -1           

數組映射解題：

class Solution {
    public int firstUniqChar(String s) {
        char[] chars = s.toCharArray();
        int base = 97;
        int[] loc = new int[26];
        for (char c:chars) loc[c - base] += 1;
        for (int i = 0; i < chars.length; i++) {
            if(loc[chars[i]-base]==1) return i;
        }
        return -1;
    }
}           

Python 基礎資料結構裡沒有 char 型，強行使用

chr(i)

轉換，隻會導緻效率更低

字元串函數解題：

利用 Java 字元串內建操作函數解題，很巧妙，效率也很高。

其中：

indexOf(): 傳回該元素第一次出現的索引，沒有則傳回 -1

lastIndex(): 傳回該元素最後一次出現的索引，沒有則傳回 -1

class Solution {
    public int firstUniqChar(String s) {
        int res = s.length();
        for (int i = 'a'; i <= 'z'; i++) {
            int firstIndex = s.indexOf((char)i);
            if (firstIndex == -1) continue;
            int lastIndex = s.lastIndexOf((char)i);
            if (firstIndex == lastIndex) {//兩次索引值相同則證明該字母隻出現一次
                res = Math.min(firstIndex, res);//res 為隻出現一次的字母中索引值最小的
            }
        }
        return res == s.length() ? -1 : res;
    }
}