[数据结构与算法][剑指 Offer 50. 第一个只出现一次的字符]

[剑指 Offer 50. 第一个只出现一次的字符]

题解：

寻找字符串中仅出现一次的字符，如果有多个仅出现一次的字符就选取的一个。

解法：

方法一：（垃圾解法，很菜，但思路和官方差不多）

定义一个LinkedHashSet保证存入数据有序且不重复，再定义一个HashSet保存重复的数据且只存放一次。

首先判断字符串大小，为零则直接返回 ‘ ’。

第一个for循环将字符串元素逐个存进LinkedHashSet，如果有重复的字符，就将重复的字符放进HashSet中保存。

第二个for循环将HashSet中的存放的重复字符给到LinkedHashSet，让LinkedHashSet把重复数据给remove删除掉，只保留在原有字符串中不重复的字符。

最后通过 if 判断，如果LinkedHashSet未空，则字符串中的数据都是重复的，返回 ‘ ’。

如果LinkedHashSet不未空，则返回LinkedHashSet存放的第一个不重复的字符。

//执行用时：22 ms, 在所有 Java 提交中击败了48.85%的用户
//内存消耗：38.9 MB, 在所有 Java 提交中击败了12.82%的用户
class Solution {
    public char firstUniqChar(String s) {
        int size = s.length();
        if (size == 0){
            return ' ';
        }
        Set<Character> res = new LinkedHashSet<Character>();
        Set<Character> temp = new HashSet<Character>();
        for (int i = 0;i < size;i++){
            Character str = s.charAt(i);
            if(!res.add(str)){
                temp.add(str);
            }else {
                res.add(str);
            }
        }
        for (Character useLess : temp){
                res.remove(useLess);
            }
        if (res.size() == 0){
            return ' ';
        }else {
            return res.iterator().next();
        }

    }
}

方法二：（官方）

方法很简单可以看代码。

一处生僻方法：Map.getOrDefault(ch, 0)，意思是如果Map中有 ch 这个Key，就去对应的value，如果没有这个Key，就取0。

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }
}