一个字符串中找到第一个只出现一次的字符

题目描述：

　　在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符。 如输入 abaccdeff，则输出 b。

输入：

　　输入有多组数据
　　每一组输入一个字符串。

输出：

　　输出第一个只出现一次的字符下标，没有只出现一次的字符则输出-1

我们这里有两种解题思路

1.蛮力法。

　　遍历数组，每找到一个字符是遍历一下整个数组，看看该字符是否存在数组下表不一致，但是ASSIC码值一样的字符还存在，如果不存在，则是返回该字符，如果存在，则继续遍历。该算法的时间复杂度为O(n*n)，显然这样的效率不是很高。

/**
     * 利用两次循环，时间复杂度O(n*n)
     * 
     * @author yfy
     * @param args
     *            需要查找的字符串
     * @param len
     *            字符串长度
     * @return 返回第一个出现一次字符的ASSIC码值，如果没有只出现一次的字符，则返回-1
     */
    int firstNotRepeatingChar(char[] args, int len) {
        int j;
        for (int i = 0; i < len; i++) {
            for (j = 0; j < len; j++) {
                if (i != j) {
                    if (args[i] == args[j]) {
                        break;
                    }
                }
            }
            // 沒有找到和这个字符相等的字符。
            if (j == len) {
                return args[i];
            }
        }
        return -1;
    }

 2.空间换时间

利用hash表，把字符串照中出现的字符，映射到hash表中，并统计每个字符出现的次数，再次遍历字符串的每次字符，直到找到第一个出现一次的字符。算法时间复杂度O(n)。

/**
     * 利用hash表，把每次字符做成对hash的映射
     * 
     * @author yfy
     * @param args   需要查找的字符串
     * @param len    字符数组长度
     * @return     返回第一个出现一次字符的ASSIC码值，如果没有只出现一次的字符，则返回-1
     */
    int firstNotRepeatingChar(char[] args, int len) {

        // 定义一个hash长度为 ASSIC码值长度+1
        int[] hash = new int[128];

        // 把字符数组映射到hash表中
        for (int i = 0; i < len; i++) {
            hash[args[i]]++;
        }

        // 再次遍历数组，找到第一个出现一次的字符。
        for (int i = 0; i < len; i++) {
            if (hash[args[i]] == 1) {
                char ch = args[i];
                return ch;
            }
        }

        // 没有找到出现出现一次的字符
        return -1;
    }

算法改进

　　在上面这个算法中，我们的时间复杂度为O(n)，但是我们要对字符数组遍历两次，如果字符数组数量很大，遍历两次还是有点多呢，可以不可以只遍历一次呢。当然是可以的，因为我们查找的ASSIC码中的字符，那么最多可能有128种字符，可以把出现过的字符按先后顺序都记录在一个字符数组中，我们第二次遍历只需要遍历这个字符数组中出现次数为一的字符。

/**
     * 利用hash表，把每次字符做成对hash的映射
     * 
     * @author yfy
     * @param args   需要查找的字符串
     * @param len    字符数组长度
     * @return        返回第一个出现一次字符的ASSIC码值，如果没有只出现一次的字符，则返回-1
     */
    int firstNotRepeatingChar2(char[] args, int len) {
        // 定义一个hash长度为 ASSIC码值长度
        int[] hash = new int[128];

        char[] exsited = new char[128];
        int count = 0;

        // 把字符数组映射到hash表中
        for (int i = 0; i < len; i++) {

            // 如果这个字符是第一次出现，则把该字符放入字符数组exsited中
            if (hash[args[i]] == 0) {
                exsited[count++] = args[i];
            }
            hash[args[i]]++;
        }

        // 遍历数组exsited，找到第一个出现一次的字符。
        for (int i = 0; i < count; i++) {
            if (hash[exsited[i]] == 1) {
                char ch = args[i];
                return ch;
            }
        }
        // 没有找到出现出现一次的字符
        return -1;
    }