d****o
发帖数: 1055 | 1 Describe a data structure for which getValue(int index), setValue(int index
, int value), and setAllValues(int value) are all O(1). |
f*****e
发帖数: 2992 | 2 keep the version # of the global value in every element. get/set compare
local version # with the most recent version number of the global variable
and update it. If local # < global #, get gets global value, and update
local value and #, set sets local value and update local version #.
index
【在 d****o 的大作中提到】
: Describe a data structure for which getValue(int index), setValue(int index
: , int value), and setAllValues(int value) are all O(1).
|
l*********8
发帖数: 4642 | 3 vector +
bool isGloballySet;
Value globalValue;
??? |
l****c
发帖数: 782 | 4 大牛，C++里面的map就可以当mashtable用吗？有区别吗？谢谢
【在 l*********8 的大作中提到】
: vector +
: bool isGloballySet;
: Value globalValue;
: ???
|
S**I
发帖数: 15689 | 5 unordered_map in C++11
【在 l****c 的大作中提到】
: 大牛，C++里面的map就可以当mashtable用吗？有区别吗？谢谢
|
g****y
发帖数: 240 | 6 struct Item
{val,
timestamp
};
vector- + Item global
|
C***U
发帖数: 2406 | 7 map和hashtable不一样
map是用tree来实现 查找时间不是O(1)的
hashtable是O(1)的查找时间
【在 l****c 的大作中提到】
: 大牛，C++里面的map就可以当mashtable用吗？有区别吗？谢谢
|
j*****o
发帖数: 394 | 8 看不懂= =
【在 g****y 的大作中提到】
: struct Item
: {val,
: timestamp
: };
: vector- + Item global
|
l****c
发帖数: 782 | 9 谢谢，那C++里的map什么时候用呢？
【在 C***U 的大作中提到】
: map和hashtable不一样
: map是用tree来实现 查找时间不是O(1)的
: hashtable是O(1)的查找时间
|
l****c
发帖数: 782 | 10 谢谢，所以说，面试的时候需要用hash时，就把unordered_map弄出来就行了，是吗？
【在 S**I 的大作中提到】
: unordered_map in C++11
|
|
|
g****y
发帖数: 240 | 11 就是vector中每个item多加一个timestamp来记录每个Item 的 modify timestamp.每次
getValue的时候，比较vector中Item存储的时间和global中存储的时间，返回较新的那
一个。
【在 j*****o 的大作中提到】
: 看不懂= =
|
d**********x
发帖数: 4083 | 12 ordered
【在 l****c 的大作中提到】
: 谢谢，那C++里的map什么时候用呢？
|
l****c
发帖数: 782 | 13 就是需要他们存储顺序的时候，是吗？谢谢
【在 d**********x 的大作中提到】
: ordered
|
Z*****Z
发帖数: 723 | 14 赞
【在 f*****e 的大作中提到】
: keep the version # of the global value in every element. get/set compare
: local version # with the most recent version number of the global variable
: and update it. If local # < global #, get gets global value, and update
: local value and #, set sets local value and update local version #.
:
: index
|
d****o
发帖数: 1055 | 15 setAll怎么实现o(1)呢？
【在 g****y 的大作中提到】
: 就是vector中每个item多加一个timestamp来记录每个Item 的 modify timestamp.每次
: getValue的时候，比较vector中Item存储的时间和global中存储的时间，返回较新的那
: 一个。
|
c****p
发帖数: 6474 | 16 setAll的时候不更新每个元素的值。
只保留一个值和操作序号。
【在 d****o 的大作中提到】
: setAll怎么实现o(1)呢？
|
d****o
发帖数: 1055 | 17 嗯，明白了。这个方法不错。
【在 c****p 的大作中提到】
: setAll的时候不更新每个元素的值。
: 只保留一个值和操作序号。
|
a*******y
发帖数: 1040 | 18 看不懂，这个是by index的get， set
【在 f*****e 的大作中提到】
: keep the version # of the global value in every element. get/set compare
: local version # with the most recent version number of the global variable
: and update it. If local # < global #, get gets global value, and update
: local value and #, set sets local value and update local version #.
:
: index
|
p*****2
发帖数: 21240 | |
j*****o
发帖数: 394 | 20 懂了。。。。好神奇。。。
这种题我肯定想不出来的。。
如果被考到。。要如实地说是我见过么。。
【在 g****y 的大作中提到】
: 就是vector中每个item多加一个timestamp来记录每个Item 的 modify timestamp.每次
: getValue的时候，比较vector中Item存储的时间和global中存储的时间，返回较新的那
: 一个。
|
|
|
a****s
发帖数: 559 | 21 map不是最本质的数据结构，它可以由tree来实现，也可以由hashtable来实现，甚至可
以用array来实现（不过performance会很差）。
同样queue, stack也不是，它们可以由link list实现，也可以由array实现。想搞复杂
点，也可以由hashtable或tree来实现（不过这属于脱裤子放P！）
【在 C***U 的大作中提到】
: map和hashtable不一样
: map是用tree来实现 查找时间不是O(1)的
: hashtable是O(1)的查找时间
|
a****s
发帖数: 559 | 22 刚想通。比如一个数组array，get/set就直接用index。他设计了一个global变量来保
存setAll的value.而后，如果get(i)，比较timestamps of global and array[i], 返
回timestamp最新的value；如果set(i,val)，更新array[i]里的value and timestamp.
【在 a*******y 的大作中提到】
: 看不懂，这个是by index的get， set
|
p*****2
发帖数: 21240 | 23
这题的难度是中等偏下吧？
【在 j*****o 的大作中提到】
: 懂了。。。。好神奇。。。
: 这种题我肯定想不出来的。。
: 如果被考到。。要如实地说是我见过么。。
|
