algorithm - 数据结构歧义

Question

我想不通这个面试问题。

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

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

他们都做你猜想他们应该做的事。限制是每个函数都在 O(1) 中。

如何设计才能使 setAll 的复杂度为 O(1)。

我考虑过为每个整数添加另一个字段，它将指向一个每次调用 setAll 时都会更改的整数。当有人调用 setAll 然后 set 然后 get 时，问题就来了。

编辑:我更改了变量的名称，这样会更清楚。另外，既然你问了，get 是假设返回 array[i]，set(index, value) 假设是将 value 值放在 array[index] 中。

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

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