[典型]387. 字元串中的第一個唯一字元-簡單

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

示例 1：

輸入: s = "leetcode"
輸出: 0      

示例 2:

輸入: s = "loveleetcode"
輸出: 2      

示例 3:

輸入: s = "aabb"
輸出: -1      

提示:

1 <= s.length <= 105
s 隻包含小寫字母      

來源：力扣（LeetCode）

連結：https://leetcode.cn/problems/first-unique-character-in-a-string

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

題解

方法一：O（2N）時間複雜度解法

思路：

1. 使用hash表記錄字元出現的次數
2. 再次周遊輸入字元串，判斷該字元在hash表中出現的次數

該解法時間複雜度為O（2*N）

代碼如下：

class Solution {
public:
  int firstUniqChar(string s) {
    // 使用hash表，時間複雜度2*N（可以使用map也可以使用數組進行映射）
    map<char, int> hash;
    for (size_t i = 0; i < s.length(); i++)
    {
      hash[s.at(i)]++;
    }

    for (size_t i = 0; i < s.length(); i++)
    {
      if (hash[s.at(i)] == 1)
      {
        return i;
      }
    }
    return -1;
  }
    
  int firstUniqChar2(string s) {
    // 使用hash表，時間複雜度2*N（可以使用map也可以使用數組進行映射）
    int arr[26] = { 0 };
    for (size_t i = 0; i < s.length(); i++)
    {
      arr[s.at(i) - 'a']++;
    }

    for (size_t i = 0; i < s.length(); i++)
    {
      if (arr[s.at(i) - 'a'] == 1)
      {
        return i;
      }
    }
    return -1;
  }
};      

方法二：O（N）時間複雜度解法

1. 使用hash表記錄字元出現的索引位置，初始化為-1。

1. 如果是第一次出現記錄索引位置
2. 如果不是第一次出現，設定為-2

1. 對hash表根據索引進行排序，找到第一個非負數

1. memset是将記憶體中的每一個byte都設定為對應的value，是以不能用memset設定
2. 要用int或者long來表示table，因為裡面存的是索引~~

int firstUniqChar(string s) {
    long table[26];
    //memset(table,-1,sizeof(table)/sizeof(long));
    for (int i = 0;i < 26;++i)
    {
        table[i] = -1;
    }
    for (int i = 0; i < s.size();++i)
    {
        int index = s[i] - 'a';
        if (table[index] == -2)
        {
            continue;
        }
        if (table[index] != -1)
        {
            table[index] = -2;
            continue;
        }
        table[index] = i;
    }
    sort(table,table+26);
    for(int i = 0;i < 26;++i)
    {
        if (table[i] == -1 || table[i] == -2)
        {
            continue;
        }
        return table[i];
    }
    return -1;
}