一道算法面试题

有下面一组数据，数据量大概有1000条左右，如何在时间复杂度是O(n)的前提下，实现分组

例如：

1  234
1  sds
2  sdsdsd
2  wwwwwww
1  ssassassww
4  sdsaass
5  234
1  skskks
.....

结果：

1 [234,sds,ssassassww,skskks]
5 [234]
2 [sds,sdsdsd]
4 [sdsaass]

二维数组策略？

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {
	public List[] groupby(String[] str) {
		List[] list = new List[str.length];
		for (int i = 0; i < str.length; i++) {
			String s = str[i];

			String str_index = s.split(":")[0];
			String value = s.split(":")[1];
			int index = Integer.parseInt(str_index);
			if (list[index] == null) {
				list[index] = new ArrayList();
			}
			list[index].add(value);
		}
		return list;
	}

	public static void main(String[] args) {
		List[] list = new Main().groupby(new String[] { "1:234", "1:sds",
				"2:sdsdsd", "2:wwwwwww", "1:ssassassww", "4:sdsaass", "5:234",
				"1:skskks" });
		for (int i = 0; i < list.length; i++) {
			List l = list[i];
			if(l!=null){
				System.out.print(i+":");
				for (Iterator iter = l.iterator(); iter.hasNext();) {
					String str = (String) iter.next();
					System.out.print(str+",");
				}
				System.out.println();
			}
		}
	}

}

-.-#  一看就是hashmap的实现么

使用hashmap后这题里的时间复杂能到O(n)？hashMap对于key的查找时间复杂度（在特殊情况下才能到O(1)）；还有外层对于各个元素的遍历（遍历n次）。

我怀疑lz是不是打错字了。

我是说这道题目，一看就是用类似hashmap的实现机制去做就行了。 也就是说仿照hashmap的源码来写。

并不是说用hashmap去解这道题。

跑下题，hashmap对于key的查找时间复杂度一直是O(1)。
外层对各个元素的遍历何解？

没错啦，应该实现数据库group by啦。

用空间换时间，申请个大小为1000的数组，直接array[i]++ 类hashmap时间。

牛，新手学习了