找第一个只出现一次的字符(Java实现及思路)

KLQ 2020-04-16 11:16:35 java常见问答 7434

下面给大家带来的内容是在一个字符串中找出第一个只出现一次的字符的Java实现以及思路,一起来具体的了解一下。

题目:

在一个字符串(0<=字符串长度<=10000,全部由字母组成)当中,找出第一个只出现一次的字符,并返回它的位置, 假如没有就返回 -1(要区分大小写)。

思路1:

hash

充分的利用每一个字母的ASCII码作hash来作为数组的index。

先用一个58长度的数组来存储每个字母出现的次数。

为什么是58?

这主要是因为A-Z对应的ASCII码是65-90,a-z对应的ASCII码值是97-122,而每个字母的index=int(word)-65,比如g=103-65=38,而数组当中具体记录的内容是这个字母出现的次数,最终遍历一遍字符串,找出第一个数组内容为1的字母即可,时间复杂度为O(n)。

代码实现:

public static int solution(String str)
{
    int[] words = new int[58];
    for (int i = 0; i < str.length(); i++)
    {
        words[((int) str.charAt(i)) - 65] += 1;
    }
    for (int i = 0; i < str.length(); i++)
    {
        if (words[((int) str.charAt(i)) - 65] == 1)
            return i;
    }
    return -1;
}

思路2

代码实现:

class Solution
{
    public:
        int FirstNotRepeatingChar(string str)
        {
            map < char, int > mp;
            for (int i = 0; i < str.size(); ++i)
                mp[str[i]]++;
            for (int i = 0; i < str.size(); ++i)
            {
                if (mp[str[i]] == 1)
                    return i;
            }
            return -1;
        }
};

思路3:(简介明了)

代码实现:

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

这种代码实现在思考清楚之后还是比较简单的,更多Java实例,可以来本站了解。