数据结构歧义
数据结构歧义
提问于 2011-05-02 20:32:37
我想不通这个面试问题。
你有一个整数数组。您需要提供另一个具有以下功能的数据结构：
int get(int index)
void set (int index, int value)
void setall(int value)他们都在做你猜到的他们应该做的事情。限制是每个函数都在O(1)中。
如何将其设计为setAll将为O(1)。
我考虑给每个整数添加另一个字段，它将指向一个整数，该整数在每次调用setAll时都会发生变化。当有人调用setAll，然后调用set，然后调用get时，问题就来了。
编辑:我更改了变量的名称，这样会更清楚。同样，既然你问了，get应该返回arrayi，set(index，value)假设把值放在arrayindex中。
在setall(index, value)之后，您应该对数组中的每个i，j执行get (get(i) == get(j) == value)。
回答 2
Stack Overflow用户
回答已采纳
发布于 2011-05-02 20:41:02
为数组中的每个元素保留一个DateTime字段(或简单的计数器)、一个setAllValue变量和一个setAllDateTime变量。对于每个集合，更新元素的日期时间/计数器。使用SetAll，更新setAllDateTime的值和DateTime。
在get中，比较SetAll的DateTime和元素的DateTime，以较新的为准，返回该值。
Stack Overflow用户
发布于 2011-05-02 20:41:06
在每个变量中存储一个“版本号”如何？
int globalValue, globalVersion;
int nextVersion;
int[] localValue, localVersion;
int get(int i) {
if (localVersion[i] > globalVersion)
return localValue[i];
else
return globalValue;
}
void set(int i, int value) {
localValue[i] = value;
localVersion[i] = nextVersion++;
}
void setAll(int value) {
globalValue = value;
globalVersion = nextVersion++;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5857154
复制相关文章
相似问题
腾讯云开发者
