題目

https://leetcode.com/problems/first-unique-character-in-a-string/

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

Example:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

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

解答

C#

public class Solution {
    public int FirstUniqChar(string s)
    {
        int[] array = new int[128];
        for (int i = 0; i < s.Length; i++)
        {
            array[s[i]]++;
        }

        for (int i = 0; i < s.Length; i++)
        {
            if (array[s[i]] == 1)
            {
                return i;
            }
        }
        return -1;
    }
}

結果

Runtime: 84 ms, faster than 96.5% of C# online submissions.

Memory Usage: 30.8 MB, less than 10.0% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

這題要找出整個字串裡，第一個只出現一次的 char 的 index。

根據 char ascii code 的特性 (以前上課都要背，不清楚的人清參考 Wiki )

• A-Z 為 65 ~ 90
• a-z 為 97 ~ 122

1. 宣告一個 int[] array, size = 128
2. 統計每個 char 的個數 (array[(int)char])
3. 再用另一個 for 迴圈去查找有沒有個數為 1 的char (array[s[i]] == 1)
   • 若 有 ，則回傳 index
   • 若 無 ，則回傳 -1

另外我這邊還是有一個快速的解法

C#

public class Solution {
    public int FirstUniqChar(string s)
    {
        for (int i = 0; i < s.Length; i++)
        {
            var c = s[i];
            if (s.IndexOf(c) == s.LastIndexOf(c))
                return i;
        }
        return -1;
    }
}

就是逐一判斷每個 char 的 IndexOf 及 LastIndexOf 是不是一樣，若 一樣 就代表它是整個 string 的 唯一值 啦！

不過這樣的寫法時間複雜度 (Time Complexity) 是 O(n^2) 唷！

因為 Index.Of 與 LastIndexOf 底層也是用迴圈 去查找。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉