题目:在一个字符串中找到第一个只出现一次的字符。如输入acbacd,则输出b。

分析:这道题是2006 年google 的一道笔试题。

由于题目与字符出现的次数有关,可以统计每个字符在该字符串中出现的次数,需要一个数据 容器存放每个字符的出现次数.
即这个容器的作用是:把一个字符映射成一个数字。想到利用字符的ASCII码,在常用的数据容器中,哈希表可实现此用途.


public class Day1 {
    /**
     * 找出一个字符串中第一个只出现一次的字符
     * 哈希表求解,时间复杂度:O(n)
     * @param str
     */
    public static void findFirst(String str) {
        if(str == null) {
            return;
        }
        int i = 0;
        char[] arr = str.toCharArray();

        int[] hashTable = new int[256];
        for(i = 0; i < 256; i++) {
            hashTable[i] = 0;
        }

        char[] hashKey = arr;
        for(i = 0; i < hashKey.length; i++) {
            int tmp = hashKey[i];// 将char 转为 int,即转为其对应的ASCAII码
            hashTable[tmp]++;
        }

        for(i = 0; i < hashKey.length; i++) {
            if(hashTable[hashKey[i]] == 1) {
                System.out.println((char)hashKey[i]);
                return; // 找出只出现一次的字符后就退出,若要都找出的话不退出就行
            }
        }
    }

    public static void main(String[] args) {
        String str = "abcdab";
        findFirst(str);
    }
}
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐