剑指 Offer 50. 第一个只出现一次的字符(leetcode每日打卡)

目录

题目描述

题解思路

上代码

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

示例 1:

输入：s = "abaccdeff"
输出：'b'
示例 2:

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

题解思路

用哈希表存储键值对的方式

key表示字符串，value表示是否为第一次出现

两次遍历即可求出

上代码

class Solution {
    public char firstUniqChar(String s) {
      Map map=new HashMap<>();
    char[] sss=s.toCharArray();
    for(char c: sss){
       map.put(c,!map.containsKey(c));
       //value 表示 添加时不包含s就为true 如果添加到相同的key就改为false
    }

    for(char c:sss){
    if(map.get(c)==true){return c;}
    }
    return ' ';
    
    }
}

执行用时：20 ms, 在所有 Java 提交中击败了64.19%的用户

内存消耗：38.4 MB, 在所有 Java 提交中击败了93.05%的用户

通过测试用例：104 / 104       

时间复杂度

O(N):N 为字符串 s 的长度；需遍历 s 两轮，使用O(N) ；HashMap 查找操作的复杂度为 O(1)；

空间复杂度

O(1): 由于题目指出 s 只包含小写字母，因此最多有 26 个不同字符，HashMap 存储需占用 O(26)=O(1) 的额外空间