|
锁定老帖子 主题：一道算法面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-10-25
上边的代码好么？输出的数组中有很多的null。我这样写了，数据结构里的那个散列表不太会实现。
String s[] = {"1:fhcnn","2:asdf","2:5gg4","3:3234","1:sds34"};
Map<Integer,List<String>> map = new HashMap<Integer,List<String>>();
int i,k;
String tmp;
for(i=0; i<s.length; i++)
{
k = Integer.parseInt(s[i].split(":")[0]);
tmp = s[i].split(":")[1];
List<String> list = map.get(k);
if(list == null){
list = new LinkedList<String>();
}
list.add(tmp);
map.put(k, list);
}
System.out.println(map.toString());
|
| 返回顶楼 | |
|
发表时间：2011-10-25
public class Test1 {
//假设1000条数据标号在1000以内，用数组存下
//否则可以使用hashmap代替数组
private int size = 1024;
private Set<String>[] array = new LinkedHashSet[size];
public void add(int key, String value) {
Set<String> set = array[key];
if(set == null) {
set = new LinkedHashSet<String>();
array[key] = set;
}
set.add(value);
}
public void print() {
for(int i=0; i<size; i+=1) {
if(array[i] != null) {
System.out.printf("%d %s \r\n",i, Arrays.toString(array[i].toArray()));
}
}
}
public static void main(String[] args) {
Test1 t = new Test1();
//手动模拟几条数据，你可以其他方式插入
t.add(1, "234");
t.add(1, "sds");
t.add(2, "sdsdsd");
t.add(2, "wwwwwww");
t.add(1, "ssassassww");
t.add(4, "sdsaass");
t.add(5, "234");
t.add(1, "skskks");
t.print();
}
}
/* output:
1 [234, sds, ssassassww, skskks]
2 [sdsdsd, wwwwwww]
4 [sdsaass]
5 [234]
*/
功能似乎实现了 但细节见到原题好把握点啊
|
| 返回顶楼 | |
|
发表时间：2011-10-25
syx278250658 写道
public class Test1 {
//假设1000条数据标号在1000以内，用数组存下
//否则可以使用hashmap代替数组
private int size = 1024;
private Set<String>[] array = new LinkedHashSet[size];
public void add(int key, String value) {
Set<String> set = array[key];
if(set == null) {
set = new LinkedHashSet<String>();
array[key] = set;
}
set.add(value);
}
public void print() {
for(int i=0; i<size; i+=1) {
if(array[i] != null) {
System.out.printf("%d %s \r\n",i, Arrays.toString(array[i].toArray()));
}
}
}
public static void main(String[] args) {
Test1 t = new Test1();
//手动模拟几条数据，你可以其他方式插入
t.add(1, "234");
t.add(1, "sds");
t.add(2, "sdsdsd");
t.add(2, "wwwwwww");
t.add(1, "ssassassww");
t.add(4, "sdsaass");
t.add(5, "234");
t.add(1, "skskks");
t.print();
}
}
/* output:
1 [234, sds, ssassassww, skskks]
2 [sdsdsd, wwwwwww]
4 [sdsaass]
5 [234]
*/
功能似乎实现了 但细节见到原题好把握点啊哥们 其实我系那个说你这个和楼上的那个HashMap有什么区别。。。
你不过写个一个Map 的实现类而已了。。。 |
| 返回顶楼 | |
|
发表时间：2011-10-25
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) |
| 返回顶楼 | |
|
发表时间：2011-10-25
richard_2010 写道 phk070832 写道 seahawk305 写道 -.-# 一看就是hashmap的实现么
使用hashmap后这题里的时间复杂能到O(n)？hashMap对于key的查找时间复杂度（在特殊情况下才能到O(1)）；还有外层对于各个元素的遍历（遍历n次）。 我怀疑lz是不是打错字了。 跑下题，hashmap对于key的查找时间复杂度一直是O(1)。 外层对各个元素的遍历何解？ 1）hashmap的实现 2）hashmap的key的查找时间为O(1) 3）外层对各个元素的遍历是指对各个entry的遍历？ |
| 返回顶楼 | |
|
发表时间：2011-10-25
最后修改：2011-10-25
raojl 写道 raojl 写道 phk070832 写道 seahawk305 写道 -.-# 一看就是hashmap的实现么
使用hashmap后这题里的时间复杂能到O(n)？hashMap对于key的查找时间复杂度（在特殊情况下才能到O(1)）；还有外层对于各个元素的遍历（遍历n次）。 我怀疑lz是不是打错字了。 没错啦，应该实现数据库group by啦。 用空间换时间，申请个大小为1000的数组，直接array[i]++ 类hashmap时间。 我不知道为什么大家想那么复杂呢？ struct Record{ int key; string value; } int count[1000] = {0}; Record array[1000] ={ {1，"223"}，{2，"sdkfjwe2"}，{}，{} ...... }; for(int i = 0; i < 1000;i ++ ) count[array[i].key] ++; 这样不就保证遍历一次嘛。o(n)的复杂度。 |
| 返回顶楼 | |
|
发表时间：2011-10-25
Map<Integer, List<String>> map = new HashMap<Integer, List<String>> ();
this.getList(map, key).add(value); |
| 返回顶楼 | |
|
发表时间：2011-10-25
看到1k就知道没什么好玩的了...直接hashMap吧..没有任何意义
|
| 返回顶楼 | |
|
发表时间：2011-10-26
多谢楼上诸位，看到大多数都是java实现的，而且借助了java的数据结构，set map等，但是不是所有语言都有这些直接使用的结构的，比如javascript的，1000条数据的话 也是很大的啊，所以需要复杂度为o(n)的前提下。
|
| 返回顶楼 | |
|
发表时间：2011-10-26
kingkan 写道 Map<Integer, List<String>> map = new HashMap<Integer, List<String>> ();
this.getList(map, key).add(value); 正解+1 |
| 返回顶楼 | |
