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

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

[LeetCode](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.

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 個數字而已

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrN5pOzcHPf6D28ECYg%2F-LrNF7S4K_QJjF3wWQ5K%2F1.jpg?alt=media\&token=6906a305-e969-4654-8e57-e2373e8e57fa)

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

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

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrN5pOzcHPf6D28ECYg%2F-LrNFI6-o_Cu_EHJ92fu%2F2.jpg?alt=media\&token=f3b366cf-b2c9-4b3d-9574-3ff3a3ed69e6)

```
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);
```

