剑指Offer：第一个只出现一次的字符

[sisterAn]

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

限制：

0 <= s 的长度 <= 50000

附赠leetcode地址：leetcode

[luweiCN]

• 首先要遍历字符创，记录每个字符出现的次数，利用Map存储字符的索引，队列存储一个数组[字符, 出现次数]
• 因为要找出的是第一个出现一次的字符，因此还需要把字符的顺序记录下来，所以自然想到了队列存储顺序

• 看了标准答案发现只要再遍历一次字符串就行，不需要队列了

  var firstUniqChar = function(s) {
  let map = new Map()
  let queue = []
  for (let i = 0; i < s.length; i++) {
      let c = s[i]
      if(map.has(c)) {
          let count = queue[map.get(c)][1]
          queue[map.get(c)][1] += 1
      } else {
          map.set(c, queue.length)
          queue.push([c, 1])
      }
  }
  
  let res = queue.filter(item => item[1] === 1)
  return res.length ? res.shift()[0] : ' '
  };

  复杂度分析：

• 时间复杂度：最坏情况遍历字符串一次，遍历队列一次，时间复杂度为O(n)
• 空间复杂度：O(n)

[7777sea]

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

    let map = {};
    let _s = ' ';
    for(let i=0; i<s.length; i++){
        if(map[s[i]]){
            map[s[i]] = map[s[i]] + 1
        }else{
            map[s[i]] = 1
        }
    }

    const _map = Object.entries(map);
    for(let j=0;j<_map.length;j++){
        if(_map[j][1] === 1){
            _s = _map[j][0];
            break
        }
    }

    return _s
};

[plane-hjh]

简单粗暴遍历

const firstUniqChar = (s) => {
  if(!s) return " "

  let list = []
  let map = {}

  for(let i = 0, len = s.length; i < len; i++) {
    map[s[i]] = map[s[i]] === undefined ? 1 : 0
  }

  for(let item in map) {
      if(map[item] === 1) {
          return item
      }
  }

  return  " "
}

[13001920223]

/**
 * @param {string} s
 * @return {character}
 */
var firstUniqChar = function(s) {
    var map = new Map();
    for (var i = 0; i < s.length; i++) {
        var subStr = s[i];
        if (map.get(subStr)) {
            map.set(subStr, 2);
        } else {
            map.set(subStr, 1);
        }
    }
    console.log(map)
    for (var key of map.keys()) {
        if (map.get(key) === 1) {
            return key;
        }
    }
    return ' ';
};

[sisterAn]

解答：使用Map

使用 map 两次遍历即可：

• 遍历字符串，将每个字符的值与出现次数记录到 map 中
• 再次遍历 map.keys() ，获取 map 中每个字符出现的次数，判断是否仅仅只有 1 次，返回第一个仅出现一次的字符

const firstUniqChar = function(s) {
    if(!s) return " "
    let map = new Map()
    for(let c of s) {
        if(map.has(c)) {
            map.set(c, map.get(c) + 1)
        } else {
            map.set(c, 1)
        }
    }
    for(let c of map.keys()) {
        if(map.get(c) === 1) {
            return c
        }
    }

    return  " "
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

leetcode

[JaniceDong]

if(!s.trim()) return " "; let obj = {}; for(var i = 0; i < s.length; i++){ let str = s[i]; if(!obj[str]){ obj[str] = 1; }else{ obj[str] += 1; } } for(var j in obj){ if(obj[j] == 1) return j; } return ' ';

[sfsoul]

解答：使用Map

使用 map 两次遍历即可：

• 遍历字符串，将每个字符的值与出现次数记录到 map 中
• 再次遍历 map.keys() ，获取 map 中每个字符出现的次数，判断是否仅仅只有 1 次，返回第一个仅出现一次的字符

var firstUniqChar = function(s) {
    if(!s) return " "
    let map = new Map()
    for(let c of s) {
        if(map.has(c)) {
            map.set(c, map.get(c) + 1)
        } else {
            map.set(c, 1)
        }
    }
    for(let c of map.keys()) {
        if(map.get(c) === 1) {
            return c
        }
    }

    return  " "
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

leetcode

不需要遍历两次。

/* 栈的思想

1. 若map中不存在则push进数组中，同时存入map中；
2. 若map中已存在，则获取值在数组中的索引并且在数组中去除该值；
3. 遍历完字符串返回数组中的第一个值即可。 */

   const fn = s => {
   const map = new Map();
   const len = s.length;
   const stack = [];
   for (let i=0; i<len; i++) {
       if (map.has(s[i])) {
           if (stack.indexOf(s[i]) > -1) {
               const idx = stack.indexOf(s[i]);
               stack.splice(idx, 1);
           }
       } else {
           stack.push(s[i]);
           map.set(s[i], i);
       }
   }
   console.log('stack', stack, 'map', map);
   return stack[0] || " ";
   }

[xiaowuge007]

`javascript function firstString(str) {

    let map = new Map();
    let obj = {}
    for(let i = 0;i<str.length;i++){
        if(obj[str[i]]){
            continue;
        }
        if(map.get(str[i])){
            map.delete(str[i]);
            obj[str[i]] = true;
        }else{
            map.set(str[i],1)
        }
    }
    return map.keys().next().value
}`

[tomorrowIsNewDay]

 function bd(str) {
  let stack = []
  let exist = []
  for(let i = 0; i < str.length; i++) {
    let index = stack.indexOf(str[i])
    if(index === -1 && !exist.includes(str[i]) ){
      stack.push(str[i])
    }else{
      stack.splice(index,1)
      exist.push(str[i])
    }
  }
  return stack.length ? stack[0] : ''
}

[JohnApache]

想了很久，还是做了两次遍历，使用 map

const firstUniqChar = (source: string) => {
    if (source.length <= 0) return ' ';
    const mapValueToIndex: Record<string, number> = {};
    const charList: (string | undefined)[] = [];
    for (let i = 0; i < source.length; i++) {
        const char = source.charAt(i);
        const index = mapValueToIndex[char];
        if (index !== undefined) {
            delete mapValueToIndex[char];
            charList[index] = undefined;
            continue;
        }
        mapValueToIndex[char] = i;
        charList[i] = char;
    }
    for (let j = 0; j < charList.length; j++) {
        if (charList[j] !== undefined) {
            return charList[j];
        }
    }

    return ' ';
};

console.log(firstUniqChar('abaccdeff'));
console.log(firstUniqChar('adbaccdeff'));
console.log(firstUniqChar(''));

// 输出
// b
// b
// ' '

[XW666]

static firstUniqChar(s) {

  let map = {}
  for (let c of s) {
    if (map[c]) {
      map[c] = map[c] + 1
    } else {
      map[c] = 1
    }
  }
  for (let c of Object.keys(map)) {
    if (map[c] === 1) {
      return c
    }
  }
  return ''
}