50. 第一个只出现一次的字符

https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
难度： #简单

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

示例 1:

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

示例 2:

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

限制：0 <= s 的长度 <= 50000

class Solution {
    public char firstUniqChar(String s) {

    }
}

解答思路1：
使用linkedHashMap,
顺序查找字符数组，
记录每种字符出现的次数，
最后取出Map中第一个出现次数为1的字符，
如果没有，则返回' '。

解答思路2：
使用int数组记录字符出现的次数，
int数组的下标对应26个小写字母，
顺序查找字符数组，
判断其是否第一次出现，
第一次出现时将其加入到新的字符数组中，
最后再根据新的字符数组中出现顺序，
遍历int数组中，
找到第一个值出现一次的字符。

解答思路3
使用Boolean数组记录字符出现与否，
Boolean数组的下标对应26个小写字母，
顺序查找字符数组，
判断其是否第一次出现，
如果Boolean数组对应的值为NULL,
则是第一次出现，将其加入到新的字符数组中，
并且设置Boolean数组对应的值为True,
如果Boolean数组对应的值为True，
则是第二次出现，修改为False,
如果Boolean数组对应的值为False，
则是第三次及以上出现，无需进行任何操作，
最后再根据新的字符数组中出现的顺序，
遍历Boolean数组中，
找到第一个值为False的字符。

package edu.yuwen.sowrd.num50.solution;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import edu.yuwen.sowrd.num50.sol3.Solution;

public class SolutionTest {
    
    @Test
    public void testCase1() {
        Solution solution = new Solution();
        String s = "abaccdeff";
        char c = solution.firstUniqChar(s);
        Assertions.assertEquals('b', c);
    }

    
    @Test
    public void testCase2() {
        Solution solution = new Solution();
        String s = "";
        char c = solution.firstUniqChar(s);
        Assertions.assertEquals(' ', c);
    }
}

package edu.yuwen.sowrd.num50.sol1;

import java.util.linkedHashMap;
import java.util.Map.Entry;

public class Solution {
    // 保存出现过的字符
    linkedHashMap char2Count = new linkedHashMap<>();

    public char firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return ' ';
        }

        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            Integer count = char2Count.get(c);
            if (count == null) {
                count = 0;
            }
            count++;
            char2Count.put(c, count);
        }

        for (Entry entry : char2Count.entrySet()) {
            // 返回第一个出现1次的字符
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }

        return ' ';
    }
}

package edu.yuwen.sowrd.num50.sol2;

public class Solution {

    // 26个小写字母出现的次数
    int[] charsCount = new int[26];

    // 字符第一次出现的顺序
    char[] firstChars = new char[26];
    int firstIndex = 0;

    public char firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return ' ';
        }

        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            int index = c - 'a';
            // 字符计数为0，则第一次出现的顺序
            if (charsCount[index] == 0) {
                // 记录出现的顺序
                firstChars[firstIndex] = c;
                firstIndex++;
            }
            // 字符出现次数加1
            charsCount[index]++;
        }

        for (int i = 0; i < firstIndex; i++) {
            char c = firstChars[i];
            int index = c - 'a';
            // 第一次只出现一次的字符
            if (charsCount[index] == 1) {
                return c;
            }
        }
        return ' ';
    }
}

package edu.yuwen.sowrd.num50.sol3;

public class Solution {
    // 下标对应的字符，值表示是否第一次出现
    Boolean[] index2Exist = new Boolean[26];

    // 字符出现的顺序
    char[] cOrder = new char[26];
    int cIndex = 0;

    public char firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return ' ';
        }
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            int index = c - 'a';
            Boolean exist = index2Exist[index];
            // 字符第一次出现
            if (exist == null) {
                cOrder[cIndex] = c;
                cIndex++;
                index2Exist[index] = true;
            }
            // 字符第二次出现
            else if (exist) {
                index2Exist[index] = false;
            }
        }

        // 按照字符出现的顺序，查找第一次出现的字符
        for (int i = 0; i < cIndex; i++) {
            char c = cOrder[i];
            int index = c - 'a';
            Boolean exist = index2Exist[index];
            if (exist) {
                return c;
            }
        }

        return ' ';
    }
}