剑指offer34——第一个只出现一次的字符

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

  • 示例
    输入
    “google”
    返回值
    4

  • 思路分析
    本题最直接最容易想到的思路就是创建一个两层的循环,第一层循环固定一个目标字符,第二层循环从整个字符串中寻找是否有与目标字符相同的字符(注意第二层循环一定要刨除目标字符本身)。若存在相同字符,则第一层循环进入下一次循环;若不存在相同字符,则输出该目标字符的下标。本方法思路简单,但时间开销较大,时间复杂度为O(n²)。

  • 实现代码

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        int position = -1;
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length(); j++) {
                if(i == j) continue;
                position = i;
                if (str.charAt(i) == str.charAt(j)) {
                    position = -1;
                    break;
                }
            }
            if (position != -1) break;
        }
        return position;
    }
}

- 改进优化
若想降低时间上的开销,本题可以采用哈希表的方法解决。因为题目中规定输入的只能为字母并区分大小写,则对应的ASCII范围为65-122,其中A-Z对应的ASCII码为65-90,a-z对应的ASCII码值为97-122。利用这58个数值分别减去65后的值作为哈希表的index,即0-57。最终遍历一遍字符串,找出第一个数组内容为1的字母就可以了,时间复杂度为O(n)。

public class Solution {
    public int FirstNotRepeatingChar(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;
       }
}
上一篇:剑指 Offer 65. 不用加减乘除做加法


下一篇:开课吧Web全栈架构师第20期-2021最新结业班