第一个只出现一次的字符

题目描述

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

解法一：

空间换时间。遍历输入字符串str，建立HashMap储存遍历到的字符串，value记录其出现的次数和最后一次的下标。最后遍历HashMap，取出现次数为1且下标最小的便是要求的字符。

public class Solution {
    public static int FirstNotRepeatingChar(String str) {
        if(str.length() <= 0 || str == null) 
            return -1;
        Map<Object, int[]> map = new HashMap<Object, int[]>();
        //将str中的字符放入map中，记录出现次数与下标
        for(int i = 0; i < str.length(); i++) {
            char m = str.charAt(i);
            if(!map.containsKey(m)) {
                int[] location = new int[2];
                location[0] = 1;
                location[1] = i;
                map.put(m, location);
            }
            else {
                int[] value = map.get(m);
                value[0]++;
                value[1] = i;
                map.put(m, value);
            }
        }
        int result = Integer.MAX_VALUE;
        //取出现次数为1且下标最小的值
        for(Entry<Object, int[]> entry : map.entrySet()) {
            int[] value = entry.getValue();
            if(value[0] == 1) {
                result = Math.min(result, value[1]);
            }
        }
        return result;
    }
}

解法二：

思路与解法一相似，也是利用HashMap记录，解法一是利用map的value同时记录次数和下标，解法二map的value只记录次数。遍历完str完成对次数的统计后，再对str进行遍历，遍历时从map获得当前字符的次数，第一个出现一次的字符便是要求的字符。

解法三：

针对该题目的特殊性，我们可以不借助java的Map，自己写一个简单的Map，由于字符型（char）的长度为16，一共有65536种可能，ASCII码表共128个字符，但是ASCII码表包含了常见字符，所以可以使用字符的ASCII码作为数组的下标，数组中存放的是该字符出现的次数。

(每种数据类型的长度，见JAVA基本数据类型所占长度)

第一次扫描str确定每个字符出现的次数，第二次扫描str找到第一个次数为1的字符。

public class Solution {
    public static int FirstNotRepeatingChar(String str) {
        if(str.length() <= 0 || str == null) 
            return -1;
        int[] mymap = new int[128];
        for(int i = 0; i < 128; i++) {
            mymap[i] = 0;
        }
        for(int i = 0; i < str.length(); i++) {
             char c = str.charAt(i);
             mymap[(int)c]++;
        }
        for(int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(mymap[(int)c] == 1) {
                return i;
            }
        }
        return -1;
    }
}

相似题目：字符流中第一个只出现一次的字符