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

java 使用数组 HashMap LinkedHashMap 三种实现方式
​
思路一：哈希表

题中有出现多少次的字眼，不难想到用哈希表，如果用HaspMap那么存储键值不能保证有序，所以取出来的第一个值为1的键值可能并不是我们要找的，这里参考了评论区的解法，不能用haspmap键值为1的字符去匹配字符串，而是以字符串字符的遍历顺序去匹配haspmap，这样就能取出第一个键值为1的字符的位置了

import java.util.HashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str.length()==0)
            return -1;
        if(str.length()==1)
            return str.charAt(0);
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i=0;i<str.length();i++)
        {
            if(map.containsKey(str.charAt(i)))
            map.put(str.charAt(i),map.get(str.charAt(i))+1);
            else
            map.put(str.charAt(i),1);
        }
        for(int i=0;i<str.length();i++)
        {
            if(map.get(str.charAt(i))==1)
            return i;
        }
        return -1;
    }
}

如果用LinkedHashMap，那么按序取出键值为1的字符即为所找的字符，因为LinkeHashMap是有序的，但是LinkedHashMap底层是链表每个节点占用了额外的空间，内存占用会高一点

import java.util.LinkedHashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str.length()==0)
            return -1;
        if(str.length()==1)
            return str.charAt(0);
        LinkedHashMap<Character,Integer> map = new LinkedHashMap<>();
        for(int i=0;i<str.length();i++)
        {
            if(map.containsKey(str.charAt(i)))
            map.put(str.charAt(i),map.get(str.charAt(i))+1);
            else
            map.put(str.charAt(i),1);
        }
        for(char ch:map.keySet())
        {
            if(map.get(ch)==1)
                return str.indexOf(ch);
        }
        return -1;
    }
}

时间O(N)+O(N)=O(N)

空间O(N)

思路二：本题我们也可以直接用数组实现，数组本身就是一种哈希表，时间和空间其实三种方法都差不多，都是O(N)，但是数组内存占用空间更小，我们知道字符本身由Ascil码表示，小写字母的ascil码的范围是65-90，大写字母为97到122，那么我们用一个长度128的数组，便可以使用数组的下标去对应字符，数组的值存放字符出现的次数

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str.length()==0)
            return -1;
        if(str.length()==1)
            return str.charAt(0);
        int map[] = new int[128];
        for(int i=0;i<str.length();i++)
        {
            map[str.charAt(i)]++;
        }
        for(int i=0;i<str.length();i++)
        {
            if(map[str.charAt(i)]==1)
                return i;
        }
        return -1;
    }
}

题目说了字符串范围都是字母不需要判断空格' '

​