问数据结构歧义

EN

我想不通这个面试问题。

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

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)。