JZ50 第一个只出现一次的字符

描述

在一个长为n字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

数据范围：0≤n≤10000，且字符串只有字母组成。 要求：

• 空间复杂度 O(n)
• 时间复杂度 O(n)

示例1

输入："google"
返回值：4

示例2

输入："aa"
返回值：-1

解法一：利用ASCII码

• a ~ z 的ASCII码：97-122
• A ~ Z 的ASCII码：65-90
• 利用字母对应的ASCII码值作为数组的下标，统计次数
• 第一次遍历统计次数
• 第二次遍历找到次数==1的字符并返回

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        
        int [] arr=new int[256];
        // 第一次循环，统计出现次数
        for(int i=0;i<str.length();i++){
            // 取得当前下标字符
            char c=str.charAt(i);  
            // 统计次数,c会自动转为ASCII码
            arr[c]++;
        }
        // 第二次循环，返回只出现一次的下标
        for(int i=0;i<str.length();i++){
            if(arr[str.charAt(i)]==1){
                return i;
            }
        }

        return -1;   
    }
}

复杂度分析

• 时间复杂度O(N)
• 空间复杂度O(1)