f*******r
发帖数: 1086 | 1 一个函数Node* Func(Node* list1, Node* list2)
输入是2个singly linked list，node datatype是int
有可能存在duplicate在input list中，要求返回一个
新的list包含在list1但是不在list2中的元素，同时要求
新的list没有duplicate。
要求，速度越快越好，可以用多余的mem。
我想了一下，最好是有一个hashtable可以记录哪些值在
list1里面，然后在loop list2去check删除那些相同的值，
有一个问题就是，这里的input datatype是int，我并不知道
数值范围，可能很大，这个题目要求coding，我应该如何建立
这样的一个hashtable? 如果用C/C++。
请大家给些建议，非常感谢了！ |
y****n
发帖数: 579 | |
f*******r
发帖数: 1086 | 3 谢谢，我有想过，不过貌似set就不是O(1)了吧取数据
而是O(logN)?
【在 y****n 的大作中提到】
: 直接用现成的c++ stl set好了。
|
p******r
发帖数: 2999 | 4 就用hashtable不行么？stl没有，可转战java
【在 f*******r 的大作中提到】
: 一个函数Node* Func(Node* list1, Node* list2)
: 输入是2个singly linked list，node datatype是int
: 有可能存在duplicate在input list中，要求返回一个
: 新的list包含在list1但是不在list2中的元素，同时要求
: 新的list没有duplicate。
: 要求，速度越快越好，可以用多余的mem。
: 我想了一下，最好是有一个hashtable可以记录哪些值在
: list1里面，然后在loop list2去check删除那些相同的值，
: 有一个问题就是，这里的input datatype是int，我并不知道
: 数值范围，可能很大，这个题目要求coding，我应该如何建立
|
f*******r
发帖数: 1086 | 5 呵呵，我不会java，所以还是考虑用C++
看来只能是用Set或者Map:)
【在 p******r 的大作中提到】
: 就用hashtable不行么？stl没有，可转战java
|
p******r
发帖数: 2999 | 6 那就写pseudo code...
【在 f*******r 的大作中提到】
: 呵呵，我不会java，所以还是考虑用C++
: 看来只能是用Set或者Map:)
|
y****n
发帖数: 579 | 7 恩，查了一下。set.find()是log（n）。
Standard C++ Library Class这个行不？ |
f*******r
发帖数: 1086 | 8 谢谢，这个看起来不错，没用过:)
查查看如何使用，如果是hash应该是O(1)
【在 y****n 的大作中提到】
: 恩，查了一下。set.find()是log（n）。
: Standard C++ Library Class这个行不？
|
