数据结构歧义

我无法确定这个采访问题。你有一个整数数组。您需要提供另一个具有以下功能的数据结构：数据结构歧义

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

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

你怎么设计它，以便setAll将是O（1）。

我想为每个整数添加另一个字段，它会指向每次调用setAll时都会更改的整数。问题出现时有人打电话setAll然后设置然后得到。

编辑：我改变了变量的名称，所以它会更清晰。另外，既然你问了，得到是假设返回数组[i]，set（index，value）假设把数值放在数组[index]中。

后setall(index, value)你应该get (get(i) == get(j) == value)为阵列中的每个i，j。

来源

2011-05-02 Eyal

什么是'i'在'set'和'setall'？ – 2011-05-02 12:35:37

我假设n =阵列的长度，效率是O（n）？ – 2011-05-02 12:35:55

为什么会有问题，如果有人卡莱特setAll，然后设置，然后得到？（按顺序，显然）此外，感觉这是一个家庭作业问题，而不是属于“面试问题”部分的问题。 – 2011-05-02 12:37:55

为数组中的每个元素，一个setAllValue变量和一个setAllDateTime变量保留一个DateTime字段（或简单地说是一个计数器）。对每一组，更新元素的日期时间/计数器。使用SetAll，更新setAllDateTime的值和DateTime。

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

来源

2011-05-02 12:41:02

谢谢！所以简单.. – Eyal 2011-05-02 14:41:29

@ Hammar的解决方案使用版本号可能更好。时间戳的问题是您依赖于没有两次更改具有相同的时间戳。这绝对取决于更改的频率和时间戳的分辨率。例如，Windows以其低准确性而闻名。 – 2011-05-02 14:51:14

@Matthieu @Hammer我认为一般情况下，你可以选择最能帮助你的答案，因为你问了这个问题，而你正在寻找一些具体的东西。在这种情况下，Hammer确实给出了一个非常好的解决方案，一个完整的答案，我同意。但我需要的是Sanrag Sood所说的。唯一的想法:)再说一次，这并不是说Hammer的回答不好:)这太棒了！ – Eyal 2011-05-04 06:04:51

如何存储 “版本号” 与每个变量，即

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

来源

2011-05-02 12:41:05 hammar

谢谢！这真是太好了.. – Eyal 2011-05-02 14:40:32

@Eyal：根据更新的数量，不要忘记处理版本循环（回到0代表未签名，并且变成负号）。 – 2011-05-02 14:49:35

这个问题说'set（i）'not'set（i，value）':-) – 2011-05-02 17:06:51

数据结构歧义

回答

相关问题