剑指offer第三十四题。

题目描述

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

解题思路

这种题目，比较容易想到的方法自然是用map来装一下，最后再遍历一遍哪个是个数为1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Map;
import java.util.LinkedHashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        //存储(值，次数)，LinkedHashMap有顺序，默认按照输入顺序排列，符合题目要求
        Map<Character,Integer> map = new LinkedHashMap<>();
        //存储(值，位置)
        Map<Character,Integer> indexMap = new LinkedHashMap<>();
        //遍历一遍进行统计
        for(int i=0;i<str.length();i++){
            if(!map.containsKey(str.charAt(i))){
                map.put(str.charAt(i),1);
                indexMap.put(str.charAt(i),i);
            }else{
                map.put(str.charAt(i),map.get(str.charAt(i))+1);
            }
        }
        //再遍历一遍找出第一个次数为1对应的位置
        for(char c:map.keySet()){
            int count = map.get(c);
            if(count == 1){
                int index = indexMap.get(c);
                return index;
            }
        }
        return -1;
    }
}

但是呢，既然题目中确定都是字母，注意区分大小写，那么就是给我们确定了范围，那么我们就可以用计数的思想来实现了。两个方法时间复杂度都一样，随便哪个都行。

我的答案

A-Z对应的ASCII码为65-90，a-z对应的ASCII码值为97-122。为了方便起见，我们设定一个65-122这个范围，统一减去65就是0-57，那么我只要准备一个长度为58的数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        //长度为58的空数组，存储对应字符的出现次数
        int[] arr = new int[58];
        //将字符串转为字符数组
        char[] strArr = str.toCharArray();
        //遍历字符数组，给对应索引处加一
        for(int i=0;i<strArr.length;i++){
            arr[strArr[i]-'A']++;
        }
        //找出第一个出现次数为1的字符的位置返回
        for(int i=0;i<strArr.length;i++){
            if(arr[strArr[i]-'A'] == 1){
                return i;
            }
        }
        return -1;
    }
}