题目分析

  1. 题目给出我们若干个字符串
  2. 我们要输出每个字符串中，只出现一次的而且是最先只出现一次的字符，如果没有的话则输出-1

方法一：哈希存储

  • 实现思路

    • 通过一个字典存储所有字符出现的次数

    • 然后按照字符串顺序遍历（可优化）

    • 找到字符串顺序中，第一个只出现一次的字符

    • 输出目标字符

    • 如果找不到则输出-1


import collections

def solution(s):
    d = collections.defaultdict(int)        # 默认字典计数
    for c in s:
        d[c] += 1                           # 统计所有字符出现的次数
    for c in s:
        if d[c] == 1:                       # 按照字符串顺序遍历字符，查看是否只出现一次
            return c
    return -1

while True:
    try:
        s = input()
        print(solution(s))
    except:
        break

复杂度分析

  • 时间复杂度：O(n)O(n)，遍历字符串的时间开销
  • 空间复杂度：O(n)O(n)，字典所花费的空间开销

方法二：哈希存储+优化

  • 实现思路
    • 对于方法一中，如果有用例"aaaaaaab"，我们就需要花很长的时间来遍历字符串直到锁定字符b才是第一次出现的只出现一次的字符
    • 因此我们再用一个seq的列表，存储字母出现过的顺序
    • 只要在一开始第一轮遍历字符串统计出现次数的时候，同时将没有见到过的字符装到seq中，我们就可以构造一个字符出现顺序的列表
    • 之后只要遍历顺序列表就可以更快锁定结果

alt

import collections

def solution(s):
    d = collections.defaultdict(int)        # 默认字典计数
    seq = list()                            # 记录字符出现顺序的列表
    for c in s:                             # 遍历给定字符串
        if c not in d:                      # 如果c没有在d中出现，此时字符c就是第一次出现的时刻
            seq.append(c)                   # 添加到顺序列表中
        d[c] += 1                           # 统计所有字符出现的次数

    for c in seq:                           # 遍历顺序列表，可以避免诸如用例"aaaaaaaab"类型的时间开销
        if d[c] == 1:                       # 按照字符串顺序遍历字符，查看是否只出现一次
            return c
    return -1

while True:
    try:
        s = input()
        print(solution(s))
    except:
        break

复杂度分析

  • 时间复杂度：O(n)O(n)，遍历字符串的时间开销
  • 空间复杂度：O(n)O(n)，字典和列表所花费的空间开销