剑指offer 50 第一个只出现一次的字符

简介: 剑指offer 50 第一个只出现一次的字符

一、题目


在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)


1.1 思路


方法一:哈希表

1、将字符当成哈希表中的key,第一次出现时候为true,重复出现则置为false;

2、遍历数组,拿到第一个在哈希表中的value为true的字符。


1.2 代码

public class FirstNotRepeatingChar {
    // google   4
    public static int FirstNotRepeatingChar(String str) {
        HashMap<Character, Boolean> map = new HashMap<>();
        char[] chars = str.toCharArray();
        // 重复的为false  不重复的为true
        for (char c : chars){
            if (map.containsKey(c)){
                map.put(c,false);
            }else {
                map.put(c,true);
            }
        }
        // 返回第一个不重复的
        for (int i = 0; i < chars.length; i++) {
            if (map.get(chars[i])){
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        String str = "google";
        System.out.println(FirstNotRepeatingChar(str));
    }
}


1.4 复杂度分析


时间复杂度 O(N)。N为字符串的长度,因为需要遍历两轮字符串,所以为2N,使用大O表示法则为O(N)。


空间复杂度 O(1)。使用到的辅助空间为哈希表的空间,由于题目给出所出现的字符为大小写字母,所以也就是说只需要占用O(32)的空间,则空间复杂度为O(1),常数级别。

目录
相关文章
|
索引
【LeetCode】917. 仅仅反转字母、387. 字符串中的第一个唯一字符
目录 917. 仅仅反转字母 387. 字符串中的第一个唯一字符
51 0
|
7月前
|
存储 索引
LeetCode 387. 字符串中的第一个唯一字符
LeetCode 387. 字符串中的第一个唯一字符
45 0
|
2月前
(剑指Offer)04、二维数组中的查找11、旋转数组的最小数字50、第一个只出现一次的字符(2021.12.02)
(剑指Offer)04、二维数组中的查找11、旋转数组的最小数字50、第一个只出现一次的字符(2021.12.02)
40 1
|
7月前
|
机器学习/深度学习 索引
【力扣】387. 字符串中的第一个唯一字符
【力扣】387. 字符串中的第一个唯一字符
|
7月前
|
机器人 Java
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
73 0
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
|
7月前
|
算法
leetcode:387. 字符串中的第一个唯一字符
leetcode:387. 字符串中的第一个唯一字符
30 0
|
7月前
|
Java Go
每日一题《剑指offer》字符串篇之字符流中第一个不重复的字符
每日一题《剑指offer》字符串篇之字符流中第一个不重复的字符
65 0
每日一题《剑指offer》字符串篇之字符流中第一个不重复的字符
|
7月前
|
Java
【剑指offer】- 第一个只出现一次的字符位置-34/67
【剑指offer】- 第一个只出现一次的字符位置-34/67
剑指offer 51. 字符串中第一个只出现一次的字符
剑指offer 51. 字符串中第一个只出现一次的字符
69 0
每日三题-无重复字符的最长子串、最长连续序列、找到字符串中所有字母异位词
每日三题 无重复字符的最长子串 最长连续序列 找到字符串中所有字母异位词
99 1
每日三题-无重复字符的最长子串、最长连续序列、找到字符串中所有字母异位词