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

HJ59 找出字符串中第一个只出现一次的字符

题目描述

找出字符串中第一个只出现一次的字符

方法一：首次末次比较解法

解题思路

针对方法一，我们记录输入字符串中每个字符第一次出现的位置和最后一次出现的位置，这样如果相等，则说明只出现了一次，不相等则不止出现一次。

解题代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    while(cin >> str)
    {
        bool flag = false;//flag用来判断是否存在只出现一次的字符
        for(int i =0;i<str.size();i++)//遍历一遍字符串
        {
            if(str.find_first_of(str[i]) == str.find_last_of(str[i]))//判断当前字符是否是只出现了一次
            {
                cout << str[i] << endl;//若是，则输出这个字符
                flag = true;
                break;//找到了第一次出现的字符，跳出循环
            }
        }
        if(!flag) cout << "-1" << endl;//如果没有找到第一次出现的字符，则输出-1
    }
    return 0;
}

复杂度分析

时间复杂度：两层循环，外层时间复杂度为O（N）,内层find_first_of()函数时间复杂度为O(N)，参考https://blog.csdn.net/laojiu_/article/details/52133072 ，因此时间复杂度为$O(N^2)O(N^2)$。

空间复杂度：没有引入新的额外内存地址空间，因此空间复杂度为$O(1)O(1)$

方法二：频数统计方法

解题思路

我们也可以使用频数统计的方法，记录字符串中每个字符出现的次数，然后再遍历一边字符串找出第一个出现一次的字符即可。

解题代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    while(cin>>str)
    {
        int count[26] = {0};
        for(int i = 0; i < str.size(); i++)//统计每个字符出现的频数
        {
            count[str[i] - 'a']++;
        }
        bool flag = false;//用户判断是否存在只出现一次的字符
        for(int i = 0; i < str.size(); i++)
        {
            if (count[str[i] - 'a'] == 1)//判断当前字符是否只出现一次
            {
                cout<<str[i]<<endl;
                flag = true;//改变flag
                break;
            }
        }
        if(!flag){//若flag为false表示不存在只出现一次的字符
            cout<<-1<<endl;
        }
    }
    return 0;
}

复杂度分析

时间复杂度：对输入字符串进行一层循环，时间复杂度为$O(N)O(N)$

空间复杂度：使用了常数大小的地址空间，因此空间复杂度为$O(1)O(1)$