题解 | #第一个只出现一次的字符#（附带图解）

思路:

从题中给出的有效信息有两点：

• 找到第一个只出现一次的字符
• 区分大小写，从0开始计数

由于哈希函数对于hash值的算法的速度比较快，故此此字符串可以通过哈希数组来进行解答

方法一：哈希数组

具体做法：
先将数据存入哈希数组中，判断存在就存 -1， 不存在就存当前下标，再通过哈希数组遍历找到最小的下标返回即可，具体过程如下图所示

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        char[] c = str.toCharArray();
        Map<Character,Integer> hm = new HashMap<Character,Integer>();
        for (int i = 0; i < c.length; i++) {
            //存在则放入，反之不放
            if(hm.containsKey(c[i])){ 
                hm.put(c[i],-1);
            }else{
                hm.put(c[i],i);
            }
        }
        int firstIndex = c.length; char firstChar = ' ';
        for (Map.Entry<Character,Integer> mn : hm.entrySet()) {
            //遍历返回 大于 -1 且 第一个出现的字符
            if(mn.getValue() > -1 && firstIndex > mn.getValue()){
                firstIndex = mn.getValue();
                firstChar = mn.getKey();
            }
        }
        return firstIndex == c.length ? -1 : firstIndex;
    }
}

复杂度分析：

• 时间复杂度：O(n)，遍历了两次，常数省略
• 空间复杂度：O(n) ，申请了常数的char数组空间

方法二：遍历n次字符串

具体做法：
遍历n次字符串，用 flag 标记当前是否为第一个出现的第一个

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        int len=str.length();
        int flag=0;//记录当前字符是否唯一
        for (int i = 0; i < len; i++) {
            for (int j =0; j < len; j++) {
                //j = i 跳过本次循环
                if(j==i) continue;
                //找到相同字符则退出循环，没有则继续遍历，直至循环结束
                if(str.charAt(i)==str.charAt(j)){
                    flag=1;
                    break;
                }
                if(str.charAt(i)!=str.charAt(j)){
                    flag=0;
                }
            }
            if(flag==0)
                return i;
        }
        return -1;
    }
}

复杂度分析：

• 时间复杂度：O(n^2) 遍历n次字符串，时间复杂度为n^2,n为字符串长度
• 空间复杂度：O(1) 未申请额外的空间