j**********3 发帖数: 3211 | 1 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
其他的都还好,这个clear操作怎么能做到O(1) 呢?
来自版上的面经。请教了很多朋友,没找到合适的solution。 |
l*********8 发帖数: 4642 | 2 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp.
只有time stamp 比valid start time新的时候,才认为 entry valid.
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
l*********8 发帖数: 4642 | 3 请问iteration o(n)是怎么做到的?
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
j**********3 发帖数: 3211 | 4 这样,是不是直接设一个boolean值更直接?
感觉不是在这个上边做文章,隐隐约约觉得应该用其他data structure,比如array或
者list什么的实现。。。
但。。。完全没思路啊。。。
.
【在 l*********8 的大作中提到】 : 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp. : 只有time stamp 比valid start time新的时候,才认为 entry valid. : : n)
|
j**********3 发帖数: 3211 | 5 我。。。以为。。。hashmap本身得就是o(n)呢?
【在 l*********8 的大作中提到】 : 请问iteration o(n)是怎么做到的? : : n)
|
r****s 发帖数: 1025 | 6 你把map底层的datastructure(array)直接set null扔掉,重新做一个新array,不就是
O(1)?
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
j**********3 发帖数: 3211 | 7 我有想过这个。但感觉不对吧?
【在 r****s 的大作中提到】 : 你把map底层的datastructure(array)直接set null扔掉,重新做一个新array,不就是 : O(1)? : : n)
|
e***l 发帖数: 710 | 8 一个boolean就行了
【在 j**********3 的大作中提到】 : 我有想过这个。但感觉不对吧?
|
d****n 发帖数: 12461 | 9 和一个空的map swap就可以了,被swap的交给gc,所以cost就不算在这个map上面了。
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
j**********3 发帖数: 3211 | 10 我就是这么想的,但后来想想,好像连boolean都不需要了。。。
直接new一个就可以了。。。
但感觉不对吧??
【在 e***l 的大作中提到】 : 一个boolean就行了
|
|
|
j**********3 发帖数: 3211 | 11 和new一个新的比,怎么样?
【在 d****n 的大作中提到】 : 和一个空的map swap就可以了,被swap的交给gc,所以cost就不算在这个map上面了。 : : n)
|
u*****n 发帖数: 126 | 12 上面思路都错了。
提示:把clear和lookup放在一起看。不是每个pointer都是valid的,怎么判断? |
j**********3 发帖数: 3211 | 13 其实,我也觉得整个思路走偏了,所以请大牛您来看看。。。
看了提示,还是不知道呀。。。。
求继续指教。。。
【在 u*****n 的大作中提到】 : 上面思路都错了。 : 提示:把clear和lookup放在一起看。不是每个pointer都是valid的,怎么判断?
|
u*****n 发帖数: 126 | 14 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新
的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是
valid 的呢? |
l*********8 发帖数: 4642 | 15 我之前思路说用time stamp, 也错了吗?
【在 u*****n 的大作中提到】 : 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新 : 的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是 : valid 的呢?
|
z*******3 发帖数: 13709 | 16 clean操作你定义一个额外的变量isclean
每次都先check这个变量
然后读写的时候要记得放timestamp
isclean一样要放timestamp
对比两个timestamp先后来决定用哪个
就是上一次clean的timestamp之前的所有数据都不可用
都应该返回空
不过这题有个取巧的方法
你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean
那是gc的事,跟你操作无关
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
l*********8 发帖数: 4642 | 17 请问zhaoce大牛, map内部是如何实现iteration O(n)的? hash table + linked
list?
【在 z*******3 的大作中提到】 : clean操作你定义一个额外的变量isclean : 每次都先check这个变量 : 然后读写的时候要记得放timestamp : isclean一样要放timestamp : 对比两个timestamp先后来决定用哪个 : 就是上一次clean的timestamp之前的所有数据都不可用 : 都应该返回空 : 不过这题有个取巧的方法 : 你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean : 那是gc的事,跟你操作无关
|
z*******3 发帖数: 13709 | 18 不牛,上面有牛,那头牛已经说了
map底层是array和list
array就可以实现o(n)的iteration了
linked
【在 l*********8 的大作中提到】 : 请问zhaoce大牛, map内部是如何实现iteration O(n)的? hash table + linked : list?
|
u*****n 发帖数: 126 | 19 抱歉没仔细看你的解法。很好的思路。
原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假
设有很大的内存,同时不必考虑collision。
设计一个Map,满足下面的时间复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示:
如果我们用randomly accessed array,复杂度如下:
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下:
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
【在 l*********8 的大作中提到】 : 我之前思路说用time stamp, 也错了吗?
|
j**********3 发帖数: 3211 | 20 就是说,设一个boolean值,然后clear了,这个map就不valid了?然后再查它,就不
valid了,那clear了之后,再想往里边塞东西怎么办呢?
【在 u*****n 的大作中提到】 : 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新 : 的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是 : valid 的呢?
|
|
|
S******1 发帖数: 216 | 21 3个数组来做,
一个a是普通的bucket, 元素存储array b 的index
一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数
组b的有效长度,a的index如果小于len就当作无效。
clear的时候set len = 0;
一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
validation.
或者两个数组,但是数组b是
class Rec {
int val;
int a'sIndex;
} |
u*****n 发帖数: 126 | 22 A binary state is insufficient
【在 j**********3 的大作中提到】 : 就是说,设一个boolean值,然后clear了,这个map就不valid了?然后再查它,就不 : valid了,那clear了之后,再想往里边塞东西怎么办呢?
|
j**********3 发帖数: 3211 | 23 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多
东西咯。然后存储空间也变大了?
【在 z*******3 的大作中提到】 : clean操作你定义一个额外的变量isclean : 每次都先check这个变量 : 然后读写的时候要记得放timestamp : isclean一样要放timestamp : 对比两个timestamp先后来决定用哪个 : 就是上一次clean的timestamp之前的所有数据都不可用 : 都应该返回空 : 不过这题有个取巧的方法 : 你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean : 那是gc的事,跟你操作无关
|
j**********3 发帖数: 3211 | 24 所以,还是不能直接用hashmap,需要用array 和 list?
【在 z*******3 的大作中提到】 : 不牛,上面有牛,那头牛已经说了 : map底层是array和list : array就可以实现o(n)的iteration了 : : linked
|
u*****n 发帖数: 126 | 25 Emm, you need one variable, but not a Boolean.
【在 j**********3 的大作中提到】 : 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多 : 东西咯。然后存储空间也变大了?
|
z*******3 发帖数: 13709 | 26 不增加复杂度
【在 j**********3 的大作中提到】 : 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多 : 东西咯。然后存储空间也变大了?
|
z*******3 发帖数: 13709 | 27 hashmap本身就是map,用map实现什么map?
【在 j**********3 的大作中提到】 : 所以,还是不能直接用hashmap,需要用array 和 list?
|
l*********8 发帖数: 4642 | 28 谢谢zhaoce和unichen!
【在 u*****n 的大作中提到】 : 抱歉没仔细看你的解法。很好的思路。 : 原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假 : 设有很大的内存,同时不必考虑collision。 : 设计一个Map,满足下面的时间复杂度。 : add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of : elements)。 : 提示: : 如果我们用randomly accessed array,复杂度如下: : add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate: : O(size of array)
|
j**********3 发帖数: 3211 | 29 哦哦。。。感觉有点混淆上边各种方法了。。我回头查一下。。
【在 u*****n 的大作中提到】 : Emm, you need one variable, but not a Boolean.
|
j**********3 发帖数: 3211 | 30 你看懂了?来解释解释呗?
【在 l*********8 的大作中提到】 : 谢谢zhaoce和unichen!
|
|
|
j**********3 发帖数: 3211 | 31 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
【在 z*******3 的大作中提到】 : hashmap本身就是map,用map实现什么map?
|
f*********5 发帖数: 576 | 32 map=null;
or
map=new HashMap<,>();
不可以吗?
【在 j**********3 的大作中提到】 : 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
|
j**********3 发帖数: 3211 | 33 上边问了。。。
ls各位大牛给解释了。。。。
虽然。。。俺也没弄明白。。。
请明白人解释一下
【在 f*********5 的大作中提到】 : map=null; : or : map=new HashMap<,>(); : 不可以吗?
|
f*********5 发帖数: 576 | 34 哪解释了
zhaoce牛也是这么答的阿
看不出来有什么问题
【在 j**********3 的大作中提到】 : 上边问了。。。 : ls各位大牛给解释了。。。。 : 虽然。。。俺也没弄明白。。。 : 请明白人解释一下
|
j**********3 发帖数: 3211 | 35 我就是说没看明白,能说说么。。。
【在 f*********5 的大作中提到】 : 哪解释了 : zhaoce牛也是这么答的阿 : 看不出来有什么问题
|
p*****2 发帖数: 21240 | 36 new一下时间复杂度多少?
new一下的cost不小吧? |
p*****2 发帖数: 21240 | 37
加timestamp能保证O(1)吗?
【在 l*********8 的大作中提到】 : 我之前思路说用time stamp, 也错了吗?
|
p*****2 发帖数: 21240 | 38
什么是randomly accessed array, 什么是sequential array?
【在 u*****n 的大作中提到】 : 抱歉没仔细看你的解法。很好的思路。 : 原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假 : 设有很大的内存,同时不必考虑collision。 : 设计一个Map,满足下面的时间复杂度。 : add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of : elements)。 : 提示: : 如果我们用randomly accessed array,复杂度如下: : add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate: : O(size of array)
|
j**********3 发帖数: 3211 | 39 我这不是也没看懂,才问的么。。。
上边讨论的解法,您看懂了么?看懂了给俺解释一下?
【在 p*****2 的大作中提到】 : : 什么是randomly accessed array, 什么是sequential array?
|
p*****2 发帖数: 21240 | 40
longway的解法比较靠谱,注意一下reuse。
【在 j**********3 的大作中提到】 : 我这不是也没看懂,才问的么。。。 : 上边讨论的解法,您看懂了么?看懂了给俺解释一下?
|
|
|
f********x 发帖数: 2086 | 41
.
意思就是clear()O(1)其实就是把valid start time设置成现在时间,则map内所有元
素都invalid了?
【在 l*********8 的大作中提到】 : 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp. : 只有time stamp 比valid start time新的时候,才认为 entry valid. : : n)
|
f********x 发帖数: 2086 | 42
这个方法,a数组里的数组怎么delete?时间长了全是无效指针了?
【在 S******1 的大作中提到】 : 3个数组来做, : 一个a是普通的bucket, 元素存储array b 的index : 一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数 : 组b的有效长度,a的index如果小于len就当作无效。 : clear的时候set len = 0; : 一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做 : validation. : 或者两个数组,但是数组b是 : class Rec { : int val;
|
p*****3 发帖数: 488 | 43
不需要delete, 小于counter的不算,还有validation array
【在 f********x 的大作中提到】 : : 这个方法,a数组里的数组怎么delete?时间长了全是无效指针了?
|
s********k 发帖数: 2352 | 44 直接用实现hashmap的算法, 稍微改动一下就好了吧?
【在 j**********3 的大作中提到】 : 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
|
d****n 发帖数: 233 | 45 use two hashmap and a globle version number.
one map store the real data, another one store the corresponding version
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
j**********3 发帖数: 3211 | 46 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
其他的都还好,这个clear操作怎么能做到O(1) 呢?
来自版上的面经。请教了很多朋友,没找到合适的solution。 |
l*********8 发帖数: 4642 | 47 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp.
只有time stamp 比valid start time新的时候,才认为 entry valid.
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
l*********8 发帖数: 4642 | 48 请问iteration o(n)是怎么做到的?
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
j**********3 发帖数: 3211 | 49 这样,是不是直接设一个boolean值更直接?
感觉不是在这个上边做文章,隐隐约约觉得应该用其他data structure,比如array或
者list什么的实现。。。
但。。。完全没思路啊。。。
.
【在 l*********8 的大作中提到】 : 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp. : 只有time stamp 比valid start time新的时候,才认为 entry valid. : : n)
|
j**********3 发帖数: 3211 | 50 我。。。以为。。。hashmap本身得就是o(n)呢?
【在 l*********8 的大作中提到】 : 请问iteration o(n)是怎么做到的? : : n)
|
|
|
r****s 发帖数: 1025 | 51 你把map底层的datastructure(array)直接set null扔掉,重新做一个新array,不就是
O(1)?
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
j**********3 发帖数: 3211 | 52 我有想过这个。但感觉不对吧?
【在 r****s 的大作中提到】 : 你把map底层的datastructure(array)直接set null扔掉,重新做一个新array,不就是 : O(1)? : : n)
|
e***l 发帖数: 710 | 53 一个boolean就行了
【在 j**********3 的大作中提到】 : 我有想过这个。但感觉不对吧?
|
d****n 发帖数: 12461 | 54 和一个空的map swap就可以了,被swap的交给gc,所以cost就不算在这个map上面了。
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
j**********3 发帖数: 3211 | 55 我就是这么想的,但后来想想,好像连boolean都不需要了。。。
直接new一个就可以了。。。
但感觉不对吧??
【在 e***l 的大作中提到】 : 一个boolean就行了
|
j**********3 发帖数: 3211 | 56 和new一个新的比,怎么样?
【在 d****n 的大作中提到】 : 和一个空的map swap就可以了,被swap的交给gc,所以cost就不算在这个map上面了。 : : n)
|
u*****n 发帖数: 126 | 57 上面思路都错了。
提示:把clear和lookup放在一起看。不是每个pointer都是valid的,怎么判断? |
j**********3 发帖数: 3211 | 58 其实,我也觉得整个思路走偏了,所以请大牛您来看看。。。
看了提示,还是不知道呀。。。。
求继续指教。。。
【在 u*****n 的大作中提到】 : 上面思路都错了。 : 提示:把clear和lookup放在一起看。不是每个pointer都是valid的,怎么判断?
|
u*****n 发帖数: 126 | 59 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新
的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是
valid 的呢? |
l*********8 发帖数: 4642 | 60 我之前思路说用time stamp, 也错了吗?
【在 u*****n 的大作中提到】 : 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新 : 的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是 : valid 的呢?
|
|
|
z*******3 发帖数: 13709 | 61 clean操作你定义一个额外的变量isclean
每次都先check这个变量
然后读写的时候要记得放timestamp
isclean一样要放timestamp
对比两个timestamp先后来决定用哪个
就是上一次clean的timestamp之前的所有数据都不可用
都应该返回空
不过这题有个取巧的方法
你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean
那是gc的事,跟你操作无关
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
l*********8 发帖数: 4642 | 62 请问zhaoce大牛, map内部是如何实现iteration O(n)的? hash table + linked
list?
【在 z*******3 的大作中提到】 : clean操作你定义一个额外的变量isclean : 每次都先check这个变量 : 然后读写的时候要记得放timestamp : isclean一样要放timestamp : 对比两个timestamp先后来决定用哪个 : 就是上一次clean的timestamp之前的所有数据都不可用 : 都应该返回空 : 不过这题有个取巧的方法 : 你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean : 那是gc的事,跟你操作无关
|
z*******3 发帖数: 13709 | 63 不牛,上面有牛,那头牛已经说了
map底层是array和list
array就可以实现o(n)的iteration了
linked
【在 l*********8 的大作中提到】 : 请问zhaoce大牛, map内部是如何实现iteration O(n)的? hash table + linked : list?
|
u*****n 发帖数: 126 | 64 抱歉没仔细看你的解法。很好的思路。
原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假
设有很大的内存,同时不必考虑collision。
设计一个Map,满足下面的时间复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示:
如果我们用randomly accessed array,复杂度如下:
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下:
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
【在 l*********8 的大作中提到】 : 我之前思路说用time stamp, 也错了吗?
|
j**********3 发帖数: 3211 | 65 就是说,设一个boolean值,然后clear了,这个map就不valid了?然后再查它,就不
valid了,那clear了之后,再想往里边塞东西怎么办呢?
【在 u*****n 的大作中提到】 : 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新 : 的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是 : valid 的呢?
|
S******1 发帖数: 216 | 66 3个数组来做,
一个a是普通的bucket, 元素存储array b 的index
一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数
组b的有效长度,a的index如果小于len就当作无效。
clear的时候set len = 0;
一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
validation.
或者两个数组,但是数组b是
class Rec {
int val;
int a'sIndex;
} |
u*****n 发帖数: 126 | 67 A binary state is insufficient
【在 j**********3 的大作中提到】 : 就是说,设一个boolean值,然后clear了,这个map就不valid了?然后再查它,就不 : valid了,那clear了之后,再想往里边塞东西怎么办呢?
|
j**********3 发帖数: 3211 | 68 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多
东西咯。然后存储空间也变大了?
【在 z*******3 的大作中提到】 : clean操作你定义一个额外的变量isclean : 每次都先check这个变量 : 然后读写的时候要记得放timestamp : isclean一样要放timestamp : 对比两个timestamp先后来决定用哪个 : 就是上一次clean的timestamp之前的所有数据都不可用 : 都应该返回空 : 不过这题有个取巧的方法 : 你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean : 那是gc的事,跟你操作无关
|
j**********3 发帖数: 3211 | 69 所以,还是不能直接用hashmap,需要用array 和 list?
【在 z*******3 的大作中提到】 : 不牛,上面有牛,那头牛已经说了 : map底层是array和list : array就可以实现o(n)的iteration了 : : linked
|
u*****n 发帖数: 126 | 70 Emm, you need one variable, but not a Boolean.
【在 j**********3 的大作中提到】 : 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多 : 东西咯。然后存储空间也变大了?
|
|
|
z*******3 发帖数: 13709 | 71 不增加复杂度
【在 j**********3 的大作中提到】 : 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多 : 东西咯。然后存储空间也变大了?
|
z*******3 发帖数: 13709 | 72 hashmap本身就是map,用map实现什么map?
【在 j**********3 的大作中提到】 : 所以,还是不能直接用hashmap,需要用array 和 list?
|
l*********8 发帖数: 4642 | 73 谢谢zhaoce和unichen!
【在 u*****n 的大作中提到】 : 抱歉没仔细看你的解法。很好的思路。 : 原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假 : 设有很大的内存,同时不必考虑collision。 : 设计一个Map,满足下面的时间复杂度。 : add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of : elements)。 : 提示: : 如果我们用randomly accessed array,复杂度如下: : add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate: : O(size of array)
|
j**********3 发帖数: 3211 | 74 哦哦。。。感觉有点混淆上边各种方法了。。我回头查一下。。
【在 u*****n 的大作中提到】 : Emm, you need one variable, but not a Boolean.
|
j**********3 发帖数: 3211 | 75 你看懂了?来解释解释呗?
【在 l*********8 的大作中提到】 : 谢谢zhaoce和unichen!
|
j**********3 发帖数: 3211 | 76 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
【在 z*******3 的大作中提到】 : hashmap本身就是map,用map实现什么map?
|
f*********5 发帖数: 576 | 77 map=null;
or
map=new HashMap<,>();
不可以吗?
【在 j**********3 的大作中提到】 : 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
|
j**********3 发帖数: 3211 | 78 上边问了。。。
ls各位大牛给解释了。。。。
虽然。。。俺也没弄明白。。。
请明白人解释一下
【在 f*********5 的大作中提到】 : map=null; : or : map=new HashMap<,>(); : 不可以吗?
|
f*********5 发帖数: 576 | 79 哪解释了
zhaoce牛也是这么答的阿
看不出来有什么问题
【在 j**********3 的大作中提到】 : 上边问了。。。 : ls各位大牛给解释了。。。。 : 虽然。。。俺也没弄明白。。。 : 请明白人解释一下
|
j**********3 发帖数: 3211 | 80 我就是说没看明白,能说说么。。。
【在 f*********5 的大作中提到】 : 哪解释了 : zhaoce牛也是这么答的阿 : 看不出来有什么问题
|
|
|
p*****2 发帖数: 21240 | 81 new一下时间复杂度多少?
new一下的cost不小吧? |
p*****2 发帖数: 21240 | 82
加timestamp能保证O(1)吗?
【在 l*********8 的大作中提到】 : 我之前思路说用time stamp, 也错了吗?
|
p*****2 发帖数: 21240 | 83
什么是randomly accessed array, 什么是sequential array?
【在 u*****n 的大作中提到】 : 抱歉没仔细看你的解法。很好的思路。 : 原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假 : 设有很大的内存,同时不必考虑collision。 : 设计一个Map,满足下面的时间复杂度。 : add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of : elements)。 : 提示: : 如果我们用randomly accessed array,复杂度如下: : add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate: : O(size of array)
|
j**********3 发帖数: 3211 | 84 我这不是也没看懂,才问的么。。。
上边讨论的解法,您看懂了么?看懂了给俺解释一下?
【在 p*****2 的大作中提到】 : : 什么是randomly accessed array, 什么是sequential array?
|
p*****2 发帖数: 21240 | 85
longway的解法比较靠谱,注意一下reuse。
【在 j**********3 的大作中提到】 : 我这不是也没看懂,才问的么。。。 : 上边讨论的解法,您看懂了么?看懂了给俺解释一下?
|
f********x 发帖数: 2086 | 86
.
意思就是clear()O(1)其实就是把valid start time设置成现在时间,则map内所有元
素都invalid了?
【在 l*********8 的大作中提到】 : 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp. : 只有time stamp 比valid start time新的时候,才认为 entry valid. : : n)
|
f********x 发帖数: 2086 | 87
这个方法,a数组里的数组怎么delete?时间长了全是无效指针了?
【在 S******1 的大作中提到】 : 3个数组来做, : 一个a是普通的bucket, 元素存储array b 的index : 一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数 : 组b的有效长度,a的index如果小于len就当作无效。 : clear的时候set len = 0; : 一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做 : validation. : 或者两个数组,但是数组b是 : class Rec { : int val;
|
p*****3 发帖数: 488 | 88
不需要delete, 小于counter的不算,还有validation array
【在 f********x 的大作中提到】 : : 这个方法,a数组里的数组怎么delete?时间长了全是无效指针了?
|
s********k 发帖数: 2352 | 89 直接用实现hashmap的算法, 稍微改动一下就好了吧?
【在 j**********3 的大作中提到】 : 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
|
d****n 发帖数: 233 | 90 use two hashmap and a globle version number.
one map store the real data, another one store the corresponding version
n)
【在 j**********3 的大作中提到】 : 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n) : 其他的都还好,这个clear操作怎么能做到O(1) 呢? : 来自版上的面经。请教了很多朋友,没找到合适的solution。
|
|
|
y**********a 发帖数: 824 | |
j**********3 发帖数: 3211 | |
y**********a 发帖数: 824 | |
j**********3 发帖数: 3211 | |
u******n 发帖数: 2 | 95
【在 S******1 的大作中提到】 : 3个数组来做, : 一个a是普通的bucket, 元素存储array b 的index : 一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数 : 组b的有效长度,a的index如果小于len就当作无效。 : clear的时候set len = 0; : 一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做 : validation. : 或者两个数组,但是数组b是 : class Rec { : int val;
|
u******n 发帖数: 2 | 96 请问这个 a bucket 是怎么实现的呢?它是一个数组吗?怎样将key和a联系在一起呢?
如果key与a的index联系,那么是不是内存不够呢?
【在 S******1 的大作中提到】 : 3个数组来做, : 一个a是普通的bucket, 元素存储array b 的index : 一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数 : 组b的有效长度,a的index如果小于len就当作无效。 : clear的时候set len = 0; : 一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做 : validation. : 或者两个数组,但是数组b是 : class Rec { : int val;
|