題目
- 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
Top comments (0)