剑指offer:第一个只出现一次的字符

题目描述
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).

创新互联基于成都重庆香港及美国等地区分布式IDC机房数据中心构建的电信大带宽,联通大带宽,移动大带宽,多线BGP大带宽租用,是为众多客户提供专业服务器托管报价,主机托管价格性价比高,为金融证券行业遂宁服务器托管,ai人工智能服务器托管提供bgp线路100M独享,G口带宽及机柜租用的专业成都idc公司。

# -*- coding: utf-8 -*-
# @Time         : 2019-07-12 9:40
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : firstNotRepeatingChar.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

from collections import defaultdict

class Solution:
    """
    由于这道题目和次数有关,因此有两种解法。
    解法1:
    遍历字符串,对于当前字符,遍历后面的所有字符,如果出现了相同的字符,那么说明这个字符出现次数>1
    这种解法的时间复杂度为O(n^2)

    解法2:
    维护一个哈希表,用于保存每个字符出现的次数。这样,通过两轮遍历,第一轮统计每个字符的出现次数,
    第二轮查询每个字符的出现次数,如果次数为1那么就返回该字符的下标。
    这种解法的时间复杂度为O(n)
    """
    def FirstNotRepeatingChar(self, s):
        if not s:
            return -1

        # 在python中,我们可以利用默认字典来简化代码
        char_count = defaultdict(int)
        for c in s:
            char_count[c] += 1

        for i in range(len(s)):
            if char_count[s[i]] == 1:
                return i

网站标题:剑指offer:第一个只出现一次的字符
网页链接:http://scyanting.com/article/jjcjpg.html