剑指Offer（三十四）-- 第一个只出现一次的字符

秦怀杂货店

发布于 2022-02-15 13:55:45

2230

发布于 2022-02-15 13:55:45

文章被收录于专栏：技术杂货店

题目描述

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

示例1

输入

"google"

返回值

4

思路以及解答

1.第一种做法：使用LinkedhashMap，key是字符，value是索引，如果里面存在该字符，则将其索引置为一个极大值（999999999），如果不存在该字符，则将该字符以及索引存放到map中。最终查找出第一个value值不为（999999999）的entry，返回其value，也就是索引，如果不存在则返回-1。

import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str==null||str.length()==0){
            return -1;
        }
        Map<Character,Integer> hashMap = new LinkedHashMap<>();
        for(int i = 0;i<str.length();i++){
            char c = str.charAt(i);
            if(hashMap.containsKey(c)){
                hashMap.put(c, 999999999);
            }else{
                hashMap.put(c,i);
            }
        }
        Map.Entry<Character,Integer> entry = hashMap.entrySet().stream().filter(e->e.getValue()!=999999999).findFirst().orElse(null);
        if(entry==null){
            return -1;
        }else{
            return entry.getValue();
        }
    }
}

2.第二种做法是，使用字符数组来统计，由于全都是字符，’A‘-’z‘一共58个字符（中间有其他字符）,比如’A‘对应下标0的元素，’B‘对应’2‘的元素。

数据里面的值，为元素出现的索引。初始化所有的值为-1，遍历字符串的字符，如果前面该字符已经存在，将其值设置为极大值（999999999)，否则设置为第一次出现的索引。

最终遍历数组，找出不为-1且不为999999999的元素，就是第一个只出现一次的字符的索引。

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

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int index = c - 'A';
            if (nums[index] >= 0) {
                nums[index] = 999999999;
            } else {
                nums[index] = i;
            }
        }
        int index = 999999999;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != -1 && nums[i] != 999999999) {
                index = Math.min(index,nums[i]);
            }
        }
        return index==999999999?-1:index;
    }

【作者简介】：秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。这个世界希望一切都很快，更快，但是我希望自己能走好每一步，写好每一篇文章，期待和你们一起交流。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-12-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自秦怀杂货店微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度