Sword to Offer-50 第一个只出现一次的字符位置 ❀

06 May 2020 in Algorithm

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

解题思路：

思路1：可用与41.2一样的方法，利用HashMap求解。

思路2：直接遍历的方法，使用一个数组来记录每个元素出现的次数。数组下标为字符，会自动转换为该字符的ASCII码，数组值为该字符出现次数。第一次遍历记录，第二次遍历找到第一个数组值为1的位置，输出即可。 两次遍历的实际下标顺序都是字符串中每个字符依次的ASCII码。

解法一、使用HashMap

AC代码：

// Get the Position of Character Appears Once in String

import java.util.HashMap;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if (str==null || str.length()==0) {
            return -1;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i=0; i<str.length(); i++) {
            char ch = str.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, 1);
            }
            else {
                map.put(ch, map.get(ch)+1);
            }
        }
        int position =0 ;
        for (position=0; position<str.length(); position++) {
            char ch = str.charAt(position);
            if (map.get(ch) == 1) {
                return position;
            }
        }
        return -1;
    }
}

解法二、使用数组

问题图解：

AC代码：

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if (str==null || str.length()==0) {
            return -1;
        }
        char[] chs = str.toCharArray();
        int[] count = new int[123];
        for (int i=0; i<chs.length; i++) {
            count[chs[i]]++;
        }
        for (int i=0; i<chs.length; i++) {
            if (count[chs[i]] == 1) {
                return i;
            }
        }
        return -1;
    }
}

补充说明：

• 注意：方法2中ASCII码字母范围65-90,98-122, 以字母ASCII码为下标储存字母出现次数，count数组大小至少要123。

• 这里是牛客编码链接