题目

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

实例:

  1. s = "leetcode"
  2. 返回 0.
s = "loveleetcode",
返回 2.

可以假定该字符串只包含小写字母。

方案一

func firstUniqChar(s string) int {
    m := map[rune]int{}
    for _, c := range s {
        m[c] = m[c] + 1
    }

    for i, c := range s {
        if v := m[c]; v == 1 {
            return i
        }
    }
    return -1
}
  • 时间复杂度 字符串中的第一个唯一字符 - 图1；
  • 由于字典遍历是按照插入顺序进行的，所以此处才没有问题。

方案二

type info struct {
    index int // 字符第一次出现索引
    count int // 字符出现次数
}

func firstUniqChar(s string) int {
    m := map[rune]*info{}
    for i, c := range s {
        if v, ok := m[c]; ok {
            v.count += 1
        } else {
            m[c] = &info {
                index: i,
                count: 1,
            }
        }
    }

    min_index := -1
    for _, v := range m {
        if v.count == 1  && (min_index == -1 || v.index < min_index) {
            min_index = v.index
        }
    }

    return min_index
}

  • 时间复杂度 字符串中的第一个唯一字符 - 图2

    方案三

    func firstUniqChar(s string) int {
  m := make([]int, 26)        // 值存出现次数
  for i:=0; i < len(s); i++ {
      m[s[i]-97]++
  }

  // 再遍历一遍字符串，找目标字符下标
  for i := 0; i < len(s); i++ {
      if m[s[i]-97] == 1 {
          return i
      }
  }

  return -1
}

    方案四（hash表+双向链表）

  1. 遍历字符串的每一个字符
  2. hash 表的 键为字符，值为链表的节点
  3. 如果重复则将该节点移动到链表尾部
  4. 遍历完毕之后判断链表的开头是否是唯一的字符串

    原文

https://leetcode-cn.com/explore/learn/card/hash-table/205/practical-application-hash-map/815/