387. First Unique Character in a String - Java 練習 - HashMap （中文解釋）

題目

• https://leetcode.com/problems/first-unique-character-in-a-string/
• https://www.geeksforgeeks.org/problems/non-repeating-character-1587115620/1 (POTD)

---

資料結構

• Hash Map

---

思路

• 將字串逐字元走訪，並用 HashMap 計數
• 因為要取得「第一個」只有一個的字元，所以再將字串逐字元走訪一次，從計數用的 HashMap 取出次數。當遇到 1 的時候就回傳該字元。

---

程式碼

以 GhG 為主。

class Solution {
    // Function to find the first non-repeating character in a string.
    static char nonRepeatingChar(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();

        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for (char c : s.toCharArray()) {
            if (map.get(c) == 1) {
                return c;
            }
        }

        return '$';
    }
}

複雜度

令 n 為字串長度。

• 時間複雜度： O(n)
  • 線性走訪兩次 - O(2n) -> O(n)
• 空間複雜度： O(n)
  • 最壞的情形是建立 key 值為 n 個的 HashMap