题解 | #第一个只出现一次的字符#

第一个只出现一次的字符

http://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c

题解一:暴力
主体思路:
选定一个字母,遍历往后所有的字母,找是否出现相同的字母:
1、将所有相同的字母设置为' ',防止后续重新被遍历到。开始下一个字母;
2、遍历完所有字母都不相同,即为最后的答案;
3、所有字母都不是唯一出现则返回-1。

图示:
图片说明

复杂度分析:
时间复杂度:O(n^2),双层循环;
空间复杂度:O(1),没有申请其他空间;
实现如下:

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        for(int i=0;i<str.size();++i){
            if(str[i]==' ')continue;//之前已经判断过不是唯一字符,无需判断;
            int flag=0;
            for(int j=i+1;j<str.size();++j){
                if(str[i]==str[j]){//相同
                    flag=1;//标记该字符不是唯一
                    str[j]=' ';//打上标记,防止后续重复判断
                }
            }
            if(!flag)return i;//唯一出现过的字符
        }
        return -1;//没有一个字符是唯一出现
    }
};

题解二:采用hash表存储字符出现频率
主要思路:
1、遍历数组,统计每个字符出现的频率,并存入hash表中;
2、遍历数组,并查询在hash表中出现的次数,当为1时,返回下标,遍历结束都没有找到返回-1;

图示:
图片说明

复杂度分析:
时间复杂度:O(n),双次循环;
空间复杂度:O(1),字母只有26个,为常数;

实现如下:

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<char,int> u_map;
        for(auto i:str){//C++11语法
           u_map[i]++;//统计每个字符的次数
        }
        for(int i=0;i<str.size();i++){
            if(u_map[str[i]]==1)return i;//找到字符出现次数唯一的情况,返回下标
        }
        return -1;//没有一个字符是唯一出现
    }
};

题解三:数组
主要思路:与题解二一样,因为都是小写字母,所以使用可以数组充当hash表的作用;
复杂度分析:
时间复杂度:O(n),双次循环;
空间复杂度:O(1),char大小256,为常数;
实现如下:

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int flag[256] = { 0 };//hash表
    for (auto i : str) {
        flag[i]++;//统计每个字符的次数
    }
    for (int i = 0; i < str.size(); ++i) {
        if (flag[str[i]] == 1)return i;//找到字符出现次数唯一的情况,返回下标
    }
    return -1;//没有一个字符是唯一出现
    }
};
牛客网编程题题解 文章被收录于专栏

本专栏记录在牛客网上AC的每一题,写下题解。 未来2年完成2000编程题的题解。 2021.12.29更新,最进准备毕设,断更了,会尽快做完毕设,继续做这一件事情

全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
Rena1ssanc...:对的,要是面评没太烂,勤更新简历等捞就行了,腾讯可以无限复活
点赞 评论 收藏
分享
06-07 17:17
嘉兴学院 教师
心爱的idea:你孩
点赞 评论 收藏
分享
07-01 17:14
中北大学 Java
兄弟们是真是假
牛客46374834...:我在boss上投java岗从来没成功过
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务