我想不通这个面试问题。
你有一个整数数组。您需要提供另一个具有以下功能的数据结构:
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)
。
发布于 2011-05-02 20:41:02
为数组中的每个元素保留一个DateTime字段(或简单的计数器)、一个setAllValue变量和一个setAllDateTime变量。对于每个集合,更新元素的日期时间/计数器。使用SetAll,更新setAllDateTime的值和DateTime。
在get中,比较SetAll的DateTime和元素的DateTime,以较新的为准,返回该值。
发布于 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++;
}
https://stackoverflow.com/questions/5857154
复制相似问题