# 387 First Unique Character in a String (有圖)

應用桶子排序 / 建立桶子 lookup = new Array(26); lookup.fill(0)

LeetCode

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

input: 給一字串
output: 找出第一個沒有重覆的字元

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    
};

如何解

丟入 Map 然後抓第一個 length = 1 的值 (Map 有順序性)

var firstUniqChar = function(s) {

  let myMap = new Map();
  for(let i = 0; i < s.length; i++){
    if(myMap.has(s[i])){
      myMap.set(s[i], myMap.get(s[i]) + 1)
    }else{
      myMap.set(s[i], 1)
    }
  }
  for(let item of myMap){
    if(item[1] == 1){
      return s.indexOf(item[0])
    }
  }
  return -1;

};
// // faster than 14.00% of JavaScript online submissions

結果速度只有 14% 好慘

改善

這題應用到桶子排序，桶子排序就是抓取速度超快，但容易浪費記憶體．不過這邊因為要存字母，字母也才 26 個數字而已

let lookup = new Array(26); // 26 個英文字母桶子
// 先全部填 0 代表裡面沒東西，
// 不然預設會是 "" 空字串, "" + 數字會變 String
lookup.fill(0);

遍歷一次 s 然後把字母放到桶子

for(let i=0; i<len;i++){
    // a 就是 97，所以就是有那個字，代表那個字的桶子數字就 + 1
    lookup[ s.charCodeAt(i) - 97 ]++; 
}

var firstUniqChar = function(s) {
  let len = s.length;
  let lookup = new Array(26); // 26 個英文字母桶子
  // 先全部填 0 代表裡面沒東西，不然預設會是 undefined, undefined + 數字會變 NaN
  lookup.fill(0);

  for(let i=0; i<len;i++){
      // a 就是 97，所以就是有那個字，代表那個字的桶子數字就 + 1
      lookup[ s.charCodeAt(i) - 97 ]++; 
  }
  for(let i=0;i<len;i++){
      if( lookup[ s.charCodeAt(i) - 97 ] === 1 ){
          return i;
      }
  }
    return -1;

};
console.log(firstUniqChar("cc"))
// faster than 80.40% of JavaScript online submissions

學到什麼

這題學到蠻多，多一個新的解題方式了就是應用桶子排序解，主要就是可以先把桶子建立起來再存相對應數量進去

let lookup = new Array(26); // 26 個英文字母桶子
// 先全部填 0 代表裡面沒東西，
// 不然預設會是 undefined, undefined + 數字會變 NaN
lookup.fill(0);