第一个只出现一次的字符

题目链接

• 牛客网

题目描述

在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

数据范围：0≤n≤10000，且字符串只有字母组成。 要求：空间复杂度O(n)，时间复杂度O(n)

刷题思路

方法一：

• 使用hashMap数据不重复特性，来标记字母出现的位置，存在则返回角标index

方案二：

• 利用indexOf()和lastIndexOf()方法，如果索引角标不一致，则多次出现

代码实现

/*
 * @Description:第一个只出现一次的字符
 * @Version: Beta1.0
 * @Author: 微信公众号：储凡
 * @Date: 2021-04-28 22:23:51
 * @LastEditors: 微信公众号：储凡
 * @LastEditTime: 2021-04-28 22:24:20
 */

/**
 * 利用indexOf和lastIndexOf角标不一致
 * @param str
 * @returns {number}
 */
function firstNotRepeatingCharOne(str) {
  const arr = str.split('')
  for (let index = 0; index < arr.length; index++) {
    if (arr.indexOf(arr[index]) === arr.lastIndexOf(arr[index])) {
      return index
    }
  }
  return -1
}

/**
 * 数组按字母查找
 * @param str
 * @returns {number}
 */
function firstNotRepeatingCharTwo(str) {
  const len = str.length
  for (let index = 0; index < len - 1; index++) {
    const s = str.slice(index, index + 1)
    const remainStr = `${str.slice(0, index)}${str.slice(index + 1)}`
    if (!remainStr.includes(s)) {
      return index
    }
  }
  return -1
}

/**
 * 使用Map结构计数
 * @param str
 * @returns {number|*}
 */
function firstNotRepeatingCharThree(str) {
  const resMap = new Map()
  const resArr = str.split('')

  // 计数操作
  resArr.forEach((r, index) => {
    if (resMap.has(r)) {
      resMap.set(r, resMap.get(r) + 1)
    }
    else {
      resMap.set(r, 1)
    }
  })

  for (const [key, value] of resMap) {
    if (value === 1) {
      return str.indexOf(key)
    }
  }
  return -1
}

console.log(firstNotRepeatingCharOne('google'))
console.log(firstNotRepeatingCharTwo('google'))
console.log(firstNotRepeatingCharThree('google'))

一些建议

• 熟练使用split、lastIndexOf、indexOf方法
• 熟练操作Map对象