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

发布时间:2020-07-21 12:30:07 作者:Jayce_SYSU
来源:网络 阅读:332

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

# -*- 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
推荐阅读:
  1. 剑指offer:字符流中第一个不重复的字符
  2. 在一个字符串中找到第一个只出现一次的字符。

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

哈希 空间换时间 第一

上一篇:你需要知道的RoketMQ

下一篇:OpenStack Train版双节点安装(十)安装网络服务neutron

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》