一道算法面试题

用一个链表数组就行了。

for
   for
这个复杂度算O(n)吗

当然算O(n)

散列，链表解决冲突.......

Java代码  收藏代码

   1. import java.util.ArrayList; 
   2. import java.util.Iterator; 
   3. import java.util.List; 
   4.  
   5. public class Main { 
   6.     public List[] groupby(String[] str) { 
   7.         List[] list = new List[str.length]; 
   8.         for (int i = 0; i < str.length; i++) { 
   9.             String s = str[i]; 
  10.  
  11.             String str_index = s.split(":")[0]; 
  12.             String value = s.split(":")[1]; 
  13.             int index = Integer.parseInt(str_index); 
  14.             if (list[index] == null) { 
  15.                 list[index] = new ArrayList(); 
  16.             } 
  17.             list[index].add(value); 
  18.         } 
  19.         return list; 
  20.     } 
  21.  
  22.     public static void main(String[] args) { 
  23.         List[] list = new Main().groupby(new String[] { "1:234", "1:sds", 
  24.                 "2:sdsdsd", "2:wwwwwww", "1:ssassassww", "4:sdsaass", "5:234", 
  25.                 "1:skskks" }); 
  26.         for (int i = 0; i < list.length; i++) { 
  27.             List l = list[i]; 
  28.             if(l!=null){ 
  29.                 System.out.print(i+":"); 
  30.                 for (Iterator iter = l.iterator(); iter.hasNext();) { 
  31.                     String str = (String) iter.next(); 
  32.                     System.out.print(str+","); 
  33.                 } 
  34.                 System.out.println(); 
  35.             } 
  36.         } 
  37.     } 
  38.  
  39. } 

List[] list = new List[str.length]; 数组易越界, new String[] { "1:234", "1:sds","2:sdsdsd", "2:wwwwwww", "1:ssassassww", "4:sdsaass", "5:234","9:skskks"}
就越界了, 可以稍微改下:
       public Map<String, List> groupByMap(String[] str){
Map<String, List> result = new HashMap<String, List>();
for(int i=0;i<str.length;i++){
String s = str[i];
String str_index = s.split(":")[0];
String value = s.split(":")[1];
if(result.get(str_index)==null){
result.put(str_index, new ArrayList());
}
result.get(str_index).add(value);
}
return result;
}


        Map<String, List> result = new Test().groupByMap(new String[]{"1:234","1:sds","2:wqer","2:wwww","1:jioasjd","4:incu","5:ojkh","8:z3ds"});
Set<String> keySet = (Set<String>)result.keySet();
for(Iterator iter = keySet.iterator();iter.hasNext();){
String strKey =(String)iter.next();
List templist = result.get(strKey);
System.out.print(strKey+":");
for(Iterator list = templist.iterator();list.hasNext();){
String str =(String)list.next();
System.out.print(str+",");
}
System.out.println();
}

你没有仔细看lz的帖子，除了有hashmap的操作，外层还有对于n个数的循环，所以总的时间复杂度（不只是hashmap的操作）不可能达到O(n) (光是外层循环就要遍历n个数，除非循环内部操作的时间复杂度为O(1),否则总的一个时间复杂度达不到O(n))

有下面一组数据，数据量大概有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




这是lz的题目，你好好看看，在内层使用hashmap查找数据并存储数据之前，你难道不需要对外层的n个输入的数进行遍历？这个题目不仅仅只有hashmap的操作。你好好看看题目吧。

另外，我关于hashmap的解释，跟你的有冲突吗？

摒弃java中 的集合类 ， 用基本的数据类型实现（除字符串外），才是正道