锁定老帖子 主题:一道算法面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-10-26
angie_hawk7 写道 多谢楼上诸位,看到大多数都是java实现的,而且借助了java的数据结构,set map等,但是不是所有语言都有这些直接使用的结构的,比如javascript的,1000条数据的话 也是很大的啊,所以需要复杂度为o(n)的前提下。
用一个链表数组就行了。 |
|
返回顶楼 | |
发表时间:2011-10-26
leon_a 写道 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(); } } } } for for 这个复杂度算O(n)吗 |
|
返回顶楼 | |
发表时间:2011-10-26
zha_zi 写道 leon_a 写道 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(); } } } } for for 这个复杂度算O(n)吗 当然算O(n) |
|
返回顶楼 | |
发表时间:2011-10-26
散列,链表解决冲突.......
|
|
返回顶楼 | |
发表时间:2011-10-26
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(); } |
|
返回顶楼 | |
发表时间:2011-10-27
jameswxx 写道 phk070832 写道 seahawk305 写道 -.-# 一看就是hashmap的实现么
使用hashmap后这题里的时间复杂能到O(n)?hashMap对于key的查找时间复杂度(在特殊情况下才能到O(1));还有外层对于各个元素的遍历(遍历n次)。 我怀疑lz是不是打错字了。 你可以把hashmap的源码好好看看,我曾经写过一篇“HashMap源码分析”的帖子。 hashmap首先根据key的hashcode进行哈希运算得到哈希值,直接根据哈希值找到链表头节点,如果链表节点长度不为1,则用equals方法比较。 hashmap的时间复杂度就是O(n)。 最好情况(所有元素hashcode不相等,equals不相等):一次哈希就得到value,时间复杂度为O(1) 最坏情况(所有元素的hashcode相等,equals不相等):一次哈希后,遍历所有的元素,时间复杂度为O(1)+O(n),还是O(n) 你没有仔细看lz的帖子,除了有hashmap的操作,外层还有对于n个数的循环,所以总的时间复杂度(不只是hashmap的操作)不可能达到O(n) (光是外层循环就要遍历n个数,除非循环内部操作的时间复杂度为O(1),否则总的一个时间复杂度达不到O(n)) |
|
返回顶楼 | |
发表时间:2011-10-27
最后修改:2011-10-27
jameswxx 写道 phk070832 写道 seahawk305 写道 -.-# 一看就是hashmap的实现么
使用hashmap后这题里的时间复杂能到O(n)?hashMap对于key的查找时间复杂度(在特殊情况下才能到O(1));还有外层对于各个元素的遍历(遍历n次)。 我怀疑lz是不是打错字了。 你可以把hashmap的源码好好看看,我曾经写过一篇“HashMap源码分析”的帖子。 hashmap首先根据key的hashcode进行哈希运算得到哈希值,直接根据哈希值找到链表头节点,如果链表节点长度不为1,则用equals方法比较。 hashmap的时间复杂度就是O(n)。 最好情况(所有元素hashcode不相等,equals不相等):一次哈希就得到value,时间复杂度为O(1) 最坏情况(所有元素的hashcode相等,equals不相等):一次哈希后,遍历所有的元素,时间复杂度为O(1)+O(n),还是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的解释,跟你的有冲突吗? |
|
返回顶楼 | |
发表时间:2011-12-06
摒弃java中 的集合类 , 用基本的数据类型实现(除字符串外),才是正道
|
|
返回顶楼 | |