首页 > 其他 > 详细

第一个只出现一次的字符

时间:2020-10-18 12:31:22      阅读:2      评论:0      收藏:0      [点我收藏+]

在一个字符串(0 <= 字符串长度 <= 10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,如果没有则返回 -1(需要区分大小写,从 0 开始计数)


解题思路

利用每个字母的 ASCII 码做 hash 来作为数组的下标。首先用一个长度为 58 的数组来存储每个字母出现的次数,为什么是 58 呢?是因为 A - Z 对应的 ASCII 码为 65-90,a - z 对应的 ASCII 码值为 97 - 122,而每个字母的 index = int(word) - 65,比如 g = 103 - 65 = 38,而数组中具体记录的内容是该字母出现的次数,最终遍历一遍字符串,找出第一个数组内容为 1 的字母就可以了,时间复杂度为 O(n)

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str == null || str.length() == 0) {
            return -1;
        }
        int[] res = new int[58];
        for(int i = 0; i < str.length(); i++) {
            res[str.charAt(i) - 65]++;
        }
        for(int i = 0; i < res.length; i++) {
            if(res[str.charAt(i) - 65] == 1) {
                return i;
            }
        }
        return -1;
    }
}

也可以使用 HashMap 来完成

import java.util.Map;
import java.util.HashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str == null || str.length() == 0) {
            return -1;
        }
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < str.length(); i++) {
            if(map.containsKey(str.charAt(i))) {
                int count = map.get(str.charAt(i));
                map.put(str.charAt(i), ++count);
            } else {
                map.put(str.charAt(i), 1);
            }
        }
        for(int i = 0; i < str.length(); i++) {
            if(map.get(str.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

第一个只出现一次的字符

原文:https://www.cnblogs.com/Yee-Q/p/13834043.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号