题意概述

• 对于给定字符串
• 找出第一个出现次数为1的字符

方法一：暴力枚举

思路与具体做法

• 对字符串两重循环
• 对每一个字符，若在字符串能找到和他相同的，则break出去
• 若找不到和他相同的，即为一个出现次数为1的字符，直接返回

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
    	int n=str.size();
        for(int i=0;i<n;i++){
        	int flag=0;
        	for(int j=0;j<n;j++){
        		if(i!=j&&str[i]==str[j]){//找到相同字符说明不是出现次数为1的元素 
        			flag=1;break;
				}
			}
			if(!flag)return i;
		} 
		return -1; 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，两重循环字符串
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅设立了几个整形变量

方法二：哈希

思路与具体做法

• 遍历两次字符串
• 第一次遍历过程中用unordered_map记录每个字符的出现次数
• 第二次遍历过程中发现第一次出现次数为一的字符则直接返回
• 没有则返回 -1

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
    	unordered_map<int,int>m;
        for(int i=0;i<str.size();i++){//用map记录每个字符的出现次数
        	m[str[i]]++;
		} 
        for(int i=0;i<str.size();i++){//发现第一次出现次数为一的字符则直接返回 
        	if(m[str[i]]==1)return i;
		} 		
        return -1;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，仅仅遍历了两次字符串
• 空间复杂度：$O\left(n\right)O(n)$O(n)，最坏情况下建立长度为字符串长度n的哈希表