一道Google2009夏季实习生招聘笔试程序设计题

最近这道题在blogjava和javaeye上出现频率很高，中午花了点时间我也实现了一下。

原题：

要求：写一个函数void count(char* input,int len)，此函数的功能是计算出一个字符串中每个字符的个数，不区分大小写，输出结果时按字符在字符串中出现的先后顺序。使用程序语言不限。
例如：input="abCc*b"，输出结果是a:1 b:2 c:2 *:1

我的java实现，借助了一个Map和两个List换时间，时间复杂度应该是O(n)：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class Google2009 {

   public static void main(String[] args) {
        BufferedReader sin = new BufferedReader(new InputStreamReader(System.in));
        String input;
        try {
            input = sin.readLine();
            new Google2009().count(input, input.length());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    public void count(String input, int len){
        HashMap<Character, Integer> charMap = new HashMap<Character, Integer>();
        ArrayList<Integer> countList = new ArrayList<Integer>();
        ArrayList<Character> charList = new ArrayList<Character>();
        input = input.toLowerCase(); 
        for(int i=0; i<len; ++i){
            char c = input.charAt(i);
            if(charMap.containsKey(c)){
                int index = charMap.get(c);
                countList.set(index, countList.get(index)+1);
            }
            else {
                charList.add(c);
                countList.add(1);
                charMap.put(c, countList.size()-1);
            }
        }
        for(int i=0; i<charList.size(); ++i){
            System.out.println(charList.get(i) + ":" + countList.get(i));
        }
    }

}