日期:2014-05-20  浏览次数:20723 次

一道笔试题(java)
求第一个无重复字符,如"total"的第一个无重复字符是o,"teeter"的第一个无重复字符是r,效率要优于O(n的平方)
public static Character FirstNonRepeated(String)

------解决方案--------------------
都是ascii字符的话比较简单,O(n)就可以了
Java code
public static Character FirstNonRepeated(String string) {
        int[] counter = new int[128];
        for (int i = 0; i < string.length(); i++) {
            char ch = string.charAt(i);
            counter[ch]++;;
        }
        for (int i = 0; i < string.length(); i++) {
            char ch = string.charAt(i);
            if(counter[ch] == 1)
                return ch;
        }
        return null;
    }