论坛首页 招聘求职论坛

一道算法面试题

浏览 13067 次
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-10-26  
angie_hawk7 写道
多谢楼上诸位,看到大多数都是java实现的,而且借助了java的数据结构,set map等,但是不是所有语言都有这些直接使用的结构的,比如javascript的,1000条数据的话 也是很大的啊,所以需要复杂度为o(n)的前提下。

用一个链表数组就行了。
0 请登录后投票
   发表时间: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)吗
0 请登录后投票
   发表时间: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)
0 请登录后投票
   发表时间:2011-10-26  
散列,链表解决冲突.......
0 请登录后投票
   发表时间: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();
}
0 请登录后投票
   发表时间: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))
0 请登录后投票
   发表时间: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的解释,跟你的有冲突吗?
0 请登录后投票
   发表时间:2011-12-06  
摒弃java中 的集合类 , 用基本的数据类型实现(除字符串外),才是正道
0 请登录后投票
论坛首页 招聘求职版

跳转论坛:
Global site tag (gtag.js) - Google Analytics