剑指 Offer 50. 第一个只出现一次的字符 (opens new window)

1.List

分析：用List集合保证插入字符的顺序性。适用String#contains方法判断重复字符。

class Solution {
    public char firstUniqChar(String s) {
        if(s.length()==0) return ' ';
        List<Character> list=new ArrayList<>();
        list.add(s.charAt(0));
        for(int i=1;i<s.length();i++){
            char c=s.charAt(i);
            if(s.substring(0,i).contains(s.substring(i,i+1))){
                if(list.contains(c))
                list.remove(Character.valueOf(c));
            }
            else{
                list.add(c);
            }
        }
        if(list.size()==0) return ' ';
        return list.get(0);
    }
}

2.LinkedHashMap

分析：LinkedHashMap保证访问顺序与插入顺序保持一致。

class Solution {
    public char firstUniqChar(String s) {
        Map<Character,Integer> map=new LinkedHashMap<>();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(map.containsKey(c)){
                map.remove(c);
                map.put(c,2);
            }
            else{
                map.put(c,1);
            }
        }
        for(Character c:map.keySet()){
           if(map.get(c)==1) return c;
        }
        return ' ';
    }
}