data-structures - 面试题：在O(1)中设置所有值的数据结构

Question

我在网上遇到了以下面试问题。

描述 getValue(int index)、setValue(int index, int value) 和 setAllValues(int value) 都是 O(1) 的数据结构。

尽管数组足以在 O(1) 中执行第一个和第二个操作，但是对于第三个（setAllValues）可以提出什么建议？

Answer 1

array一个元组怎么样{timestamp, value}，还有一个{timestamp, value}叫做all. 由于您只关心插入的相对时间，因此您可以id对时间戳的值使用单调递增：

type Entry {
  int timestamp, 
  int value
}

type structure {
    int     id
    Entry   all
    Entry[] array
}

将所有字段初始化为 0。那么以下内容应该适合您：

• 设置值（索引 i，值 v）：

  array[i] = {id++, value}
  

• 值获取值（索引 i）

  if(all.timestamp > array[i].timestamp) return all.value
  else return array[i].value
  

• 全部设置（值 v）

  all = {id++, value}
  

这种方法的一个问题是最终您将用完时间戳的 id，并且可能会回绕。如果您选择 64 位值来存储时间戳，那么这会在此发生之前为您提供 18,446,744,073,709,551,616 次插入或 setAlls。根据数据结构的预期用途，O(n) 清理阶段可能是合适的，或者您可以只抛出异常。

另一个可能需要考虑的问题是多线程。三个明显的问题：

• 如果id++不是原子的并且两个线程同时获得了一个新线程id，那么您可以获得两个具有相同 id 的条目。
• 如果 id 的增量和创建的元组的分配不是原子的（它们可能不是）并且有两个同时插入，那么您可能会得到一个较旧的 id 获胜的竞争条件。
• 如果元组的分配不是原子的，并且与insert()a 同时存在，get()那么您可能最终会处于您在数组中拥有发言权的位置{new_id, old_value}，从而导致返回错误的值。

如果其中任何一个是问题，最简单的解决方案是在文档中放入“非线程安全”（作弊）。或者，如果您不能以您选择的语言原子地实现这些方法，则需要在它们周围放置某种同步锁。

Answer 2

我在一次技术面试中得到了同样的问题。
这是我完整的即用型 Java 实现，包括测试用例。

关键思想是将 的值保留setAll()在特殊变量（例如joker）中，然后以适当的方式跟踪该值的变化。

为了保持代码干净，一些访问修饰符已被废除。

节点类：

import java.time.LocalDate;

class Node {

    int value;
    LocalDate jokerSetTime;

    Node(int val, LocalDate jokSetTime) {
        value = val;
        jokerSetTime = jokSetTime;
    }
}

DS类：

class DS {

    Node[] arr;

    DS(int len) {
        arr = new Node[len];
    }
}

数据结构类：

import java.time.LocalDate;

class DataStructure {

    private boolean isJokerChanged;
    private Integer joker;
    private LocalDate jokerSetTime;
    private DS myDS;

    DataStructure(int len) {
        myDS = new DS(len);
    }

    Integer get(int i) {

        Integer result;

        if (myDS.arr.length < i) {
            return null;
        }

        // setAll() has been just called
        if (isJokerChanged) {
            return joker;
        }

        if (myDS.arr[i] == null) {

            // setAll() has been previously called
            if (joker != null) {
                result = joker;
            } else {
                result = null;

            }

        } else if (myDS.arr[i].jokerSetTime == jokerSetTime) {
            // cell value has been overridden after setAll() call
            result = myDS.arr[i].value;
        } else {
            result = joker;
        }

        return result;
    }

    void setAll(int val) {
        isJokerChanged = true;
        joker = val;
        jokerSetTime = LocalDate.now();
    }

    void set(int i, int val) {
        isJokerChanged = false;
        myDS.arr[i] = new Node(val, jokerSetTime);
    }
}

主类：

class Main {

    public static void main(String[] args) {

        DataStructure ds = new DataStructure(100);

        Integer res;

        res = ds.get(3);

        ds.set(3, 10);

        res = ds.get(3);

        ds.setAll(6);

        res = ds.get(3);

        res = ds.get(15);

        ds.set(4, 7);

        res = ds.get(4);

        res = ds.get(3);

        ds.setAll(6);

        ds.set(8, 2);

        res = ds.get(3);
    }
}

更新：
代码已更新。之前的实现没有考虑setAll()连续两次调用相同值，后面跟着set(x),的情况get(y)，例如：setAll(100), set(3, 1), setAll(100), set(5, 3), get(3)。

添加了时间戳方法的使用，以允许区分setAll()具有相同值的不同调用。

PS 这个实现不是线程安全的。

Answer 3

指向单个公共值的指针数组怎么样？设置值，所有引用都将指向 O(1) 中的单个更改值。

Answer 4

我最近在一次采访中被问到这个问题。我想出了一个哈希表实现。它将解决时间戳值用完的问题，但需要实现线程安全功能（可能使用延迟初始化技术）

假设在我们的类中，我们有一个私有变量_defaultValue来保存默认值，我们还有一个私有哈希表或字典_hashtable。 SetAllValues可以将_defaultValue设置为等于传递的值，并将_hashtable初始化/设置为新的哈希表，并丢弃对旧哈希表的任何引用。如果键（或索引）已存在于_hashtable中，则SetValue应该只向_hashtable添加一个新值或更新该值。GetValue应该检查键（或索引）是否存在于_hashtable中，然后返回它，否则返回存储在_defaultValue。

这是我在 StackOverflow 上的第一个答案。我在编写代码时有点懒惰。可能会很快编辑答案。

面试官对这个解决方案点头同意，但坚持不使用哈希表来实现它。我想，他是在要求我给出与蒂莫西回答类似的方法。那时我无法得到它:(。无论如何，干杯！

编辑：发布代码（在 C# 中）

class MyDataStruct
{
    private int _defaultValue;
    private Dictionary<int,int> _hashtable;

    public MyDataStruct()
    {
        _defaultValue = 0; // initialize default with some value
        _hashtable = new Dictionary<int, int>();
    }

    public void SetAllValues(int val)
    {
        _defaultValue = val;
        _hashtable = new Dictionary<int, int>();
    }

    public void SetValue(int index, int val)
    {
        if (_hashtable.ContainsKey(index))
        {
            _hashtable.Add(index, val);
        }
        else
        {
            _hashtable[index] = val;
        }
    }

    public int GetValue(int index)
    {
        if (_hashtable.ContainsKey(index))
        {
            return _hashtable[index];
        }
        else
        {
            return _defaultValue;
        }
    }
}

Answer 5

我们可以有一个变量 V，它存储一个 int 和一个包含元组的数组作为 {Value, id}..

以及一个全局 int 变量 G（其作用类似于 SQL 中的标识，并且每当执行任何 set 或 setAll 操作时，其值都会增加 1）

初始所有 Ids 和 V 值将默认为 null ..

so V = null All Tuple = {null, null}
set(index i, val v) -> G = G+1, arr[i].Val = v, arr[i].Id = G

get(index i) -> if V.Id > arr[i].Id return V.Val else return arr[i]



set-all(val v) -> G= G+1, V.Id= G, V.Val = v

Answer 6

所有现有答案都使用在每次setVal操作时递增的时间戳。这不是必需的。事实上，只需要在 上增加时间戳setAll。有人提出的另一个问题是算术溢出。这可以通过更新每个单元格上的单个单元格setAll并仔细执行时间比较来处理，而不会打破恒定的时间界限。

这个怎么运作

基本概念与其他答案基本相似，但有所不同。

他们的工作：分别存储用于最后一次setAll操作的值，并跟踪执行该操作的时间。每次他们执行 asetVal时，他们将当前时间与给定值一起存储在数组中。每次他们执行 agetVal时，他们都会将给定位置的时间与上次setAll发生的时间进行比较，然后选择该位置的setAll值或取决于哪个值更大的值。

为什么这可能是一个问题：假设当前时间溢出并且setAll不久之后发生了操作。看起来好像大多数存储的数组值都比值新setAll，但实际上它们更旧。

解决方案：停止想象我们正在跟踪自数据结构初始化以来经过的总时间。想象一个带有“秒针”的巨型时钟，它不是绕圈 60 圈，而是绕圈圈 2^n 圈。秒针的位置代表最近一次setAll操作的时间。每个setVal操作都将这个时间与一个值一起存储。因此，如果我们setAll在“时钟”为 45 时执行 a，然后setVal对不同的元素执行六次操作，则setAll所有六个位置的时间和时间都将相同。我们希望保持以下不变量：

setAll当且仅当该元素的设置setVal比上一次操作更新时，给定元素位置的时间才等于时间setAll。

显然，上述过程自动确保如果元素是最近设置的，则其时间将等于setAll时间。挑战在于使相反的含义也成立。

待续 ....

编码

我用 Haskell 写了这个，因为这是我最了解的语言，但它并不是最适合这项工作的语言。

{-# LANGUAGE BangPatterns #-}
module RepArr where

import Control.Monad.Primitive
import Data.Primitive.MutVar
import qualified Data.Vector.Mutable as V
import Data.Vector.Mutable (MVector)
import Control.Applicative
import Prelude hiding (replicate)
import Control.Monad.ST
import Data.Word

-- The Int in the MutVar is the refresh pointer
data RepArr s a = RepArr (MutVar s (Word, a, Int)) (MVector s (Word,a))

-- Create a fancy array of a given length, initially filled with a given value
replicate :: (PrimMonad m, Applicative m) => Int -> a -> m (RepArr (PrimState m) a)
replicate n a = RepArr <$> newMutVar (0,a,0) <*> V.replicate n (0,a)

getVal :: PrimMonad m => RepArr (PrimState m) a -> Int -> m a
getVal (RepArr allv vec) n = do
  (vectime, vecval) <- V.read vec n
  (alltime, allval, _) <- readMutVar allv
  if (fromIntegral (alltime - vectime) :: Int) > 0
    then return allval
    else return vecval

setVal :: PrimMonad m => RepArr (PrimState m) a -> Int -> a -> m ()
setVal (RepArr allv vec) i v = do
  (!alltime, _, _) <- readMutVar allv
  V.write vec i (alltime, v)

setAll :: PrimMonad m => RepArr (PrimState m) a -> a -> m ()
setAll r@(RepArr allv vec) v = do
  (oldt, _, oldc) <- readMutVar allv
  getVal r oldc >>= setVal r oldc
  let !newc = case oldc+1 of
        op1 | op1 == V.length vec -> 0
            | otherwise -> op1
  let !newt = oldt+1
  writeMutVar allv (newt, v, newc)

为了避免潜在的（罕见的）垃圾收集暂停，实际上有必要拆箱Int和Word值，以及使用拆箱的向量而不是多态的向量，但我并没有真正的心情，这是一项相当机械的任务。

这是 C 中的一个版本（完全未经测试）：

#include <malloc.h>

struct Pair {
  unsigned long time;
  void* val;
};

struct RepArr {
  unsigned long allT;
  void* allV;
  long count;
  long length;
  struct Pair vec[];
};

struct RepArr *replicate (long n, void* val) {
  struct RepArr *q = malloc (sizeof (struct RepArr)+n*sizeof (struct Pair));
  q->allT = 1;
  q->allV = val;
  q->count = 0;
  q->length = n;

  int i;
  for (i=0; i<n; i++) {
    struct Pair foo = {0,val};
    q->vec[i] = foo;
  }
  return q;
}


void* getVal (struct RepArr *q, long i) {
  if ((long)(q->vec[i].time - q->allT) < 0)
    return q->allV;
  else
    return q->vec[i].val;
}

void setVal (struct RepArr *q, long i, void* val) {
  q->vec[i].time = q->allT;
  q->vec[i].val = val;
}

void setAll (struct RepArr *q, void* val) {
  setVal (q, q->count, getVal (q, q->count));
  q->allV = val;
  q->allT++;
  q->count++;
  if (q->count == q->length)
    q->count = 0;
}

Answer 7

/*

在我写这篇文章的时候，这个页面上的所有解决方案都会使存储数组所需的空间量增加一倍（或更多）。以下解决方案将浪费的空间量从 Ω(n) 减少到 θ(n/w)，其中 w 是计算机“字”中的位数。在我的机器上，这是 64。

此答案中的此散文位于 C 注释中，因此您可以逐字复制并粘贴此答案并使用 C 编译器对其进行编译。

*/

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

/*

问题是支持在 O(1) 时间内读取和写入数组中的值，以及在 O(1) 时间内一次写入数组中的所有值的批量写入。据我所知，这可以通过 Aho、Hopcroft 和 Ullman 发明的技术实现。由于Gonzalo Navarro，我将介绍一个版本，“小空间中的恒定时间数组初始化”。

这个想法是将三个元数据数组与数据数组一起保留。我们还保留了两个整数：unset，这是在批量写入操作中使用的最后一个值，以及size，自上次批量写入以来已设置的值的数量的近似值。在任何时候，自上次批量写入以来写入的不同值的数量都在sizew *之间size。

三个元数据数组描述了有关数据数组中 w 值块的信息。他们是：

• nth: nth[i] 是自上次批量写入以来要写入的第 i 个唯一块

• inverse_nth: inverse_nth[i] 是数组的第 i 个块的写入顺序，在最后一次批量写入时从 0 开始计数。

• bitsetbitset[i]:当编号为 64*i + j 的数组单元自上次批量写入后已写入时，第 j 位为 1。

bitset[i]如果不是集合 { , , ... , }的成员，inverse_nth[i]则允许无效。换句话说， 和是有效的当且仅当 和。inth[0]nth[1]nth[size-1]inverse_nth[i]bitset[i]inverse_nth[i] < sizenth[inverse_nth[i]] == i

我没有存储三个长度相同的单独数组，而是选择存储一个is_set包含三个字段的数组。

*/

typedef struct {
  int nth_;
  int inverse_nth_;
  uint64_t bitset_;
} IsSetCell;

typedef struct {
  int unset_;
  int size_;
  IsSetCell is_set_[];
} IsSetArray;

typedef struct {
  IsSetArray * metadata_;
  int payload_[];
} ResettableArray;

/*

要构造一个数组，我们需要一个默认值，以便在读取一个从未写入过的值时返回。

*/

ResettableArray * ConstructResettableArray(int n, int unset) {
  ResettableArray* result =
      malloc(offsetof(ResettableArray, payload_) + n * sizeof(int));
  if (!result) return NULL;
  n = (n + 63) / 64;
  result->metadata_ =
      malloc(offsetof(IsSetArray, is_set_) + n * sizeof(IsSetCell));
  if (!result->metadata_) {
    free(result);
    return NULL;
  }
  result->metadata_->size_ = 0;
  result->metadata_->unset_ = unset;
  return result;
}

void DestructResettableArray(ResettableArray * a) {
  if (a) free(a->metadata_);
  free(a);
}

/*

该算法的大部分内容是写入和读取元数据。在 定义IsSet()和Set()定义之后（如下），读取和写入数组很简单。

*/

bool IsSet(const IsSetArray * a, int i);
void Set(IsSetArray * a, int i);

int GetValue(const ResettableArray * a, int i) {
  if (!IsSet(a->metadata_, i)) return a->metadata_->unset_;
  return a->payload_[i];
}

void SetValue(ResettableArray * a, int i, int v) {
  a->payload_[i] = v;
  Set(a->metadata_, i);
}

void SetAllValues(ResettableArray * a, int v) {
  a->metadata_->unset_ = v;
}

/*

读写的复杂部分是 和 之间的双向inverse_nth关系nth。如果它们在位置 i ( ) 处相互指向，is_set[is_set[i].inverse_nth].nth == i则位置 i 包含在最后一次批量写入之后写入的有效数据，只要is_set[i].inverse_nth < size.

*/

uint64_t OneBit(int i) {
  return UINT64_C(1) << i;
}

bool IsSet(const IsSetArray * a, int i) {
  const int cell = i/64, offset = i & 63;
  const int inverse_nth = a->is_set_[cell].inverse_nth_;
  return inverse_nth < a->size_ && a->is_set_[inverse_nth].nth_ == cell &&
         a->is_set_[cell].bitset_ & OneBit(offset);
}

void Set(IsSetArray * a, int i) {
  const int cell = i/64, offset = i & 63;
  const int inverse_nth = a->is_set_[cell].inverse_nth_;
  if (inverse_nth >= a->size_ || a->is_set_[inverse_nth].nth_ != cell) {
    a->is_set_[cell].inverse_nth_ = a->size_;
    a->is_set_[cell].bitset_ = 0;
    a->is_set_[a->size_].nth_ = cell;
    ++a->size_;
  }
  a->is_set_[cell].bitset_ |= OneBit(offset);
}

Answer 8

C#中的正确解决方案：

public sealed class SpecialDictionary<T, V>
{
    private Dictionary<T, Tuple<DateTime, V>> innerData;
    private Tuple<DateTime, V> setAllValue;
    private DateTime prevTime;

    public SpecialDictionary()
    {
        innerData = new Dictionary<T, Tuple<DateTime, V>>();
    }
    public void Set(T key, V value) => innerData[key] = new Tuple<DateTime, V>(GetTime(), value);
    public void SetAll(V value) => setAllValue = new Tuple<DateTime, V>(GetTime(), value);
    public V Get(T key)
    {
        Tuple<DateTime, V> tmpValue = innerData[key];
        if (setAllValue?.Item1 > tmpValue.Item1)
        {
            return setAllValue.Item2;
        }
        else
        {
            return tmpValue.Item2;
        }
    }
    private DateTime GetTime()
    {
        if (prevTime == null)
        {
            prevTime = DateTime.Now;

        }
        else
        {
            if (prevTime == DateTime.Now)
            {
                Thread.Sleep(1);
            }
            prevTime = DateTime.Now;
        }
        return prevTime;
    }
}

和测试：

static void Main(string[] args)
{
    SpecialDictionary<string, int> dict = new SpecialDictionary<string, int>();
    dict.Set("testA", 1);
    dict.Set("testB", 2);
    dict.Set("testC", 3);
    Console.WriteLine(dict.Get("testC"));
    dict.SetAll(4);
    dict.Set("testE", 5);
    Console.WriteLine(dict.Get("testC"));
    Console.WriteLine(dict.Get("testE"));
    Console.ReadKey();
}

Answer 9

Python 示例

class d:
    def __init__(self, l):
        self.len = l
        self.g_p = [i for i in range(self.len)]
        self.g_v = [0 for i in range(self.len)]
        self.g_s = self.len - 1
        self.g_c = 0  

    def getVal(self, i):
        if (i < 0 or i >= self.len):
            return

        if (self.g_p[i] <= self.g_s):
            return self.g_v[self.g_p[i]]

        return self.g_c

    def setVal(self, i, v):
        if (i < 0 or i >= self.len):
            return

        if (self.g_p[i] > self.g_s):
            self.g_s += 1

            self.g_p[self.g_s], self.g_p[i] = self.g_p[i], self.g_p[self.g_s]

        self.g_v[self.g_p[i]] = v

    def setAll(self, v):
        self.g_c = v
        self.g_s = -1

Answer 10

关于蒂莫西·琼斯的回答：

这种方法的一个问题是最终您将用完时间戳的 id，并且可能会回绕。如果您选择 64 位值来存储时间戳，那么这会在此发生之前为您提供 18,446,744,073,709,551,616 次插入或 setAlls。根据数据结构的预期用途，O(n) 清理阶段可能是合适的，或者您可以只抛出异常。

这正是使该解决方案也成为 O(n) 而不是 O(1) 的最坏情况。这种结构虽然节省了很多潜在的 O(n) 插入操作，但仍然处于 O(n) 效率。

Answer 11

这是我在 Java 中的答案（我不完全确定语法）。为了避免 changeT 和 defChangeT 相等的情况，我做了 set-functions 同步。

Struct ValueSt{ 
  int value;
  Timestamp changeT;
}

Class MyDS{
  int default;
  Timestamp defChangeT;
  HashMap map;

  public MyDS(){
    map = new HashMap<int, ValueSt>();
  }

  public synchronized void mySet(Int key, int value){
    ValueSt vs = new ValueSt(value, Timestamp(System.current));
    map.put(key, vs);
  }

  public synchronized void setAll(int value){
    default = value;
    defChangeT = Timestamp(System.current));
  }

  public int myGet(int key){
    ValueSt vs = map.get(key);
    if(vs != null){
      if(vs.changeT > defChangeT)
        return vs.value;
      else
        return default;
    }
    return null;
  }
}

Answer 12

我最近遇到了类似的问题。我使用的数据结构是hashmap和hashset的组合。

1) setValue(String key, String value) 在这个方法中，我直接在 hashmap 中插入了对。我们还将键插入哈希集中

2) setAllValue(String Value) 在这个方法中，我重新初始化了 hashmap。这会删除所有对，然后添加一个键，比如 <"god"> 和 value。hashset 具有跨所有版本的 hashmap 维护的键集。

3) getValue(String key) 在这个方法中，我维护了多个 if/else 条件来返回值。

1. 如果键存在于哈希图中，我检查条件，然后返回该键的值。如果尚不存在“上帝”键并且每个键都保留其原始值，或者存在“上帝”键但该键的值已被覆盖，则可能会发生这种情况。
2. 一个 else/if 条件来检查该键是否不存在于哈希集中，然后返回 null，因为该键从未存在于哈希映射或映射的任何先前实例中。
3. 最后是一个else 条件，其中我返回键 <"god"> 的值，因为这意味着该键存在于某个版本的 hashmap 中并且尚未被覆盖。

类优化地图 {

Map<String, String> mymap = new HashMap<String>();
Set<String> myset = new HashSet<>();
public void setValue (String key, String value) {
    mymap.put(key, value);
    myset.add(key);
}

public void setAllValue (String value) {
    mymap = new HashMap<>();
    mymap.put("god", value);
}

public String getValue (String key) {
    if (mymap.containsKey(key)) {
        return mymap.get(key);
    } else if (!myset.contains(key)) {
        return null;
    } else {
        return mymap.get(key);
    }
}

public static void main (String args[]) {

    OptimisedMap opmap = new OptimisedMap();
    String value = opmap.getValue("hey");
    if (value == null) {
        System.out.println("Key not present");
    }
    opmap.setValue("hey", "there");
    opmap.setValue("ho", "there");
    System.out.println(opmap.getValue("hey")); // will print there
    opmap.setAllValue("whatsup");
    System.out.println(opmap.getValue("hey")); // will print whatsup
    System.out.println(opmap.getValue("ho")); // will print whatsup
    opmap.setValue("hey", "there");
    System.out.println(opmap.getValue("hey")); // will print there
    System.out.println(opmap.getValue("ho")); // will print whatsup
}

}

Answer 13

另一个 Python 示例：

    class SetAll:
    def __init__(self):
        self.mapping = {}
        self.is_all_same = True
        self.all_value = None
        self.set_all_ran = False

    def set(self, index, value):
        if self.is_all_same:
            if value == self.all_value:
                return
            else:
                self.is_all_same = False
                self.mapping[index] = value
        else:
            self.mapping[index] = value

    def get(self, index):
        if self.mapping.get(index, None):
            return self.mapping[index]
        else:
            if self.is_all_same:
                return self.all_value
            else:
                if self.set_all_ran:
                    return self.all_value
        return

    def set_all(self, value):
        self.mapping = {}
        self.is_all_same = True
        self.set_all_ran = True
        self.all_value = value

Answer 14

我在 C# 中针对这个问题的实现：

   public class MyStruct
    {
    public MyStruct(int val)
    {
        this.value = val;
        this.currentTime = 0;
    }
    public int value { get; set; }
    public int currentTime { get; set; }
}

public class Struct
{
    public List<MyStruct> array = new List<MyStruct>();
    public MyStruct all = new MyStruct(0);

    public int GetValue(int index)
    {
        if(all.currentTime >= array[index].currentTime)
        {
            return all.value;
        }
        else
        {
            return array[index].value;
        }
    }

    public void Set(int index, int value)
    {
        if(array.Count <= index)
        {
            array.Add(new MyStruct(value));
        }
        else
        {
            array[index].value = value;
        }
        array[index].currentTime = all.currentTime +1;
    }

    public void SetAll(int value)
    {
        all.value = value;
        all.currentTime++;
    }

    public void Delete(int index)
    {
        array[index].currentTime = 0;
        array[index].value = -1;
    }
}

陈卢加斯

Answer 15

好吧，我是根据事件来做的。看看这个。

internal class Program
{
    public static void Main(string[] args)
    {
        SomeUsefullDataStructure ds = new SomeUsefullDataStructure();
        
        ds.SetValue(1, "11");
        ds.SetValue(2, "22");
        var result = ds.GetValue(2);
        ds.SetAllValues("haha");

        Console.ReadKey();
    }
}

public class SomeUsefullDataStructure
{
    private delegate void SetValueDelegate(string newValue);
    private event SetValueDelegate SetValueEventFired;
    private Dictionary<int, StringDataEntry> dict = new Dictionary<int, StringDataEntry>();

    public string GetValue(int key)
    {
        if (dict.ContainsKey(key))
        {
            return dict[key].StringValue;
        }
        
        throw new ArgumentException("no such key");
    }

    public void SetValue(int key, string value)
    {
        if (dict.ContainsKey(key))
        {
            dict[key].UpdateValue(value);
        }
        else
        {
            StringDataEntry stringDataEntry = new StringDataEntry(value);
            SetValueEventFired += stringDataEntry.UpdateValue;
            dict.Add(key, stringDataEntry);
        }
    }

    public void SetAllValues(string value)
    {
        SetValueEventFired(value);
    }
}

public class StringDataEntry
{
    public string StringValue { get; private set; }

    public StringDataEntry(string value)
    {
        StringValue = value;
    }
    
    public void UpdateValue(string newValue)
    {
        StringValue = newValue;
    }
}

Answer 16

许多解决方案都很棒，但没有一个提到最先进的解决方案。

它的操作具有O(1) 的最差时间复杂度 （调用fill(v)将数组中的所有值设置为 v，并且读/写是不言自明的）， 同时除了数组之外只占用1 位额外空间。是的。fill(v), read(i), write(i, v)

因此，大小为 1,000,000 的 int32_t 数组将需要 O(1) 最坏时间来初始化（和填充），
并且只需要 32,000,001 位内存。

它在In-Place Initializable Arrays论文中提到，并在我写的一篇关于该主题的文章
中进行了解释。

我编写了一个名为Farray的纯C++ 标头库，其中包含Fillable Array，
它是上述论文的模板化实现。

Answer 17

我的 Python 解决方案。经测试。不是线程安全的。如果您发现任何问题，请告诉我:)

class TimestampedNode:
    def __init__(self, timestamp, val):
        self.timestamp = timestamp
        self.val = val

class SetAllDS:
    def __init__(self):
        self.items = []
        self.timestamp = 0
        self.all_joker= TimestampedNode(self.timestamp, 0)

    def getValue(self, index):
        try:
            item=self.items[index]
        except IndexError:
            return None
        if item.timestamp<self.all_joker.timestamp:
            return self.all_joker.val
        return item.val

    def setValue(self, index, val):
        # if index<0 or index>=len(self.items): #
        #     raise IndexError("Invalid index\n")
        self.timestamp += 1
        self.items[index]=TimestampedNode(self.timestamp, val)

    def setAllValues(self, val):
        self.timestamp+=1
        self.all_joker=TimestampedNode(self.timestamp, val)

Answer 18

这是另一个 python 解决方案：这是一个链接！

from datetime import datetime
from typing import Any, Dict


class ValueNode:
    def __init__(self, value):
        self.value = value
        self.date_updated = datetime.now()

    def set_value(self, value):
        self.value = value
        self.date_updated = datetime.now()

    def get_value(self, value):
        return self.value


class Structure:
    def __init__(self):
        self._structure: Dict[Any, ValueNode] = {}
        self._set_all_node: ValueNode = None

    def get_val(self, index):
        if self._set_all_node and self._structure.get(index) and self._structure.get(index).date_updated < self._set_all_node.date_updated:
            return self._set_all_node.value
        else:
            if index in self._structure:
                return self._structure[index].value
            else:
                return None

    def set_val(self, index, value):
        self._structure[index] = ValueNode(value)

    def set_all(self, value):
        self._set_all_node = ValueNode(value)


s1 = Structure()
s1.set_val(1, 'green')
s1.set_val(5, 'blue')
s1.set_val(9, 'yellow')
print(s1.get_val(1))
print(s1.get_val(5))
print(s1.get_val('NotExistedValue'))
s1.set_all('black')
print(s1.get_val(1))
print(s1.get_val(5))
print(s1.get_val('NotExistedValue'))