剑指offer面试题系列

题目

在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出b。

思路

如果按照常规的思路则为设立一个辅助数组，里面存放所有扫描过的字符的次数，则这种算法的时间复杂度为O(n^2).

因为每一次遍历到新的字符，都要在辅助数组里面扫描一遍，如果没有，则加上此字符，如果有则统计次数累加。

所以这样是不太满足面试官要求的。

换一种思路：哈希。

如果能在O(1)的时间复杂度下，确定是否已经遍历过该字符，岂不快哉！而这正是哈希表的擅长的地方。

思路是这样的：

因为 ASCII 字符总数只有 256 个。所以辅助数组的长度只要常数级即可。

然后确定映射算法：此处采用了最简单的，直接将其减去 a 字符的值即可，这样为了能从辅助数组的 0 位置开始存储。

初始化辅助数组都为 0.然后如果哈希后的下标处的值不为 0 ，则说明已经遍历过了，将其拉黑，此处设立一个特殊字符 ‘#’。如果为 0 ，说明还没有存放字符，则存放之。

遍历完毕，辅助数组的第一个没有被拉黑的字符即为题目要求。

算法时间复杂度：O(n),空间复杂度为O(1)。

代码

package com.ans;
//空间复杂度为O(1),时间复杂度为O(n)
public class Solution3 {
    public static char firstChar(String input) {
        char[] arr = new char[256];
        for(int k = 0 ; k < arr.length; k++) {
            arr[k] = '0';
        }
        char[] ch = input.toCharArray();
        char retChar = '$';
        int index = 0;
        for( int i = 0; i < ch.length ; i++) {
            index = IndexFor(ch[i]);
            System.out.println("Index is:" + index);
            if(arr[index] == '0') {//如果该位置上没有字符，映射到相应的位置上
                arr[index] = ch[i];
            }
            else {
                arr[index] = '#';
            }
        }

        for( int j = 0; j < arr.length; j++) {
            if(arr[j] != '#') {
                retChar = arr[j];
                break;
            }
        }


        return retChar;
    }

    public static int IndexFor(char c) {
        if(!Character.isLetter(c)) {
            System.out.println("输入不符合规范");
            return -1;
        }
        return c - 'a';
    }

    public static void main(String[] args) {

        String input = "abbaccddddeff";
        char tmp;
        if((tmp = firstChar(input)) != '$') {
            System.out.println("第一个出现一次的字符是：" + tmp );
        } else {
            System.out.println("没有找到这样的字符");
        }

    }
}

总结

哈希。