DEV Community

vc7
vc7

Posted on

1

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

題目


資料結構

  • 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 '$';
    }
}
Enter fullscreen mode Exit fullscreen mode

複雜度

令 n 為字串長度。

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

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay