LeetCode刷题【面试题50】第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = "abaccdeff"
输出：'b'

示例 2:

输入：s = "" 
输出：' '

限制：

0 <= s 的长度 <= 50000

1. 声明一个HashMap<Character,Integer> firstShowMap记录各个字符第一次出现的位置
2. 声明一个HashSet<Character> moreThenOneSet保存出现超过一次的字符
3. 遍历一遍字符串完成上面两个哈希集合的赋值
4. 遍历firstShowMap，对比moreThenOneSet处理只有出现一次的字符
5. 声明firstSingle保存单个的字符和firstSingleIndex对应的出现位置
6. 遍历firstShowMap的过程中如果找到一个新的只出现过一次的字符，两者比较firstSingleIndex，留下位置跟靠前的那一个

代码

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character,Integer> firstShowMap = new HashMap<>();
        HashSet<Character> moreThenOneSet = new HashSet<>();
        int i = -1;
        while (++i < s.length()){
            if (!firstShowMap.containsKey(s.charAt(i))){
                firstShowMap.put(s.charAt(i),i);
            }else{
                moreThenOneSet.add(s.charAt(i));
            }
        }

        final char[] firstSingle = {' '};
        final int[] firstSingleIndex = {s.length()};
        firstShowMap.forEach((theChar,theIndex)->{
            if (!moreThenOneSet.contains(theChar)){
                if (theIndex < firstSingleIndex[0]){
                    firstSingleIndex[0] = theIndex;
                    firstSingle[0] = theChar;
                }
            }
        });
        return firstSingle[0];
    }
}

思路就是这样，实现形式有很多种
比如

1. firstSingleIndex也可以不存下来，直接回firstShowMap中取到
2. 又或者官方题解中说的那样的moreThenOneSet可以省略，有重复的直接修改firstShowMap对应的value为一个不合理的值，后面判断的时候也就根据这个不合理的值来判断。

21年11月30日，重新做了一次这个题目

class Solution {
    public char firstUniqChar(String s) {
        if (s.length()==0){
            return ' ';
        }
        //重复的
        boolean[] map1 = new boolean[26];
        //第一次出现的位置
        int[] map2 = new int[26];
        Arrays.fill(map2,-1);
        int idx = -1;
        while (++idx < s.length()){
            int charIdx = s.charAt(idx)-'a';
            if (!map1[charIdx]){
                if (map2[charIdx] != -1){
                    map1[charIdx] = true;
                    map2[charIdx] = -1;
                }else{
                    map2[charIdx] = idx;
                }
            }
        }
        char ans = ' ';
        int min = s.length();
        for (int i = 0; i < map2.length; i++) {
            if (map2[i] != -1 &&  map2[i] < min){
                min = map2[i];
                ans = s.charAt(min);
            }
        }
        return ans;
    }
}

再次思考，也可以不用两个map，在一个map上定义更多的状态来实现，除了现有的-1表示默认没处理的情况，也可以再定一个-2为已经有多个相同字符出现的情况