数据结构模糊

Question

我无法想象这个面试问题.

你有一个整数数组.您需要提供另一个具有以下功能的数据结构:

int get(int index)
void set (int index, int value)
void setall(int value)

他们都做了你猜他们想做的事情.限制是每个函数都在O(1)中.

如何设计它以使setAll为O(1).

我想为每个整数添加另一个字段,这将指向每次调用setAll时都会更改的整数.当有人调用setAll然后设置然后获取时,问题就来了.

编辑:我更改了变量的名称,以便更清楚.另外,既然你问过,get假设返回array [i],设置(index,value)假设把值放在array [index]中.

在setall(index, value)你应该get (get(i) == get(j) == value)为数组中的每个i,j之后.

Answer 1

如何存储每个变量的"版本号",即

 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++;
 }

Answer 2

将DateTime字段(或简称为计数器)与数组中的每个元素,setAllValue变量和setAllDateTime变量保持一致.使用每个集合,更新元素的DateTime/counter.使用SetAll,更新setAllDateTime的值和DateTime.

在get中,将SetAll的DateTime与元素的DateTime进行比较,以较新者为准,返回该值.