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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer34——第一个只出现一次的字符，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1406字，纯文字阅读大概需要3分钟。

内容图文

• 题目描述
  在一个字符串(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;
       }
}

内容总结

以上是互联网集市为您收集整理的剑指offer34——第一个只出现一次的字符全部内容，希望文章能够帮你解决剑指offer34——第一个只出现一次的字符所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---