面试官：设计一个基于索引，setAll() 时间复杂度为 O(1) 的数据结构，要求是...

一、序

大家好，这里是承香墨影！

面试中，我们并不总是能碰到 Leetcode 上的原题，而在考教数据结构的时候，也不总是让你讲讲 HashMap 背后的存储数据的数据结构。

今天就给大家带来一道设计数据结构的面试题，设计一个存取的时间复杂度都为 O(1) 的数据结构，当然它会存在一些限制，解题需要一些技巧。

题目是这样的，设计一个数据结构，包含 3 个方法。

class {
 value getValue(index)
 void setValue(index, value)
 void setAllValue(value)
}

设计要求：

1. setValue() 可对某个具体 index 索引的值进行修改；
2. getValue() 可根据 index 索引获取对应的 Value；
3. setAllValue() 可将当前所有的 index 对应的 value 都改为传入的值；
4. 这 3 个方法的时间复杂度都是 O(1)；*

其中要求 4 才是难点，看到这里建议大家先思考一下解题思路再继续阅读。

操作效果如下，注意并非最终数据结构。

二、解题

2.1 审题

相信大家看到这个题目时，心里就有了一个粗略的认识，基于 index，可以使用 Key-Value 键值对的结构存储，例如 HashMap。也可以利用 Array 等具有 index 索引下表直查的数据结构。

这道题唯一需要技巧的点在于，如何让 setAllValue() 也保持 O(1) 的时间复杂度。如果采用遍历去修改所有 index 的值，那最少也是一个 O(n) 的线性时间复杂度。

这里用到的大 O 复杂度表示法，是一种抽象的分析方法，可在不执行代码的情况下，粗略的分析出代码的执行效率。

O(1) 的时间复杂度为常数时间复杂度，也就是它是一个常量，是不以数据量的增长而波动的时间复杂度。

通常我们可以认为，没有循环、递归等的代码，都属于 O(1) 的时间复杂度，如果循环、递归有固定的次数与层数，也属于 O(1) 时间复杂度。

int calA(int n){
  return n + 100;
}

int calB(int n){
 int value = 1;
 for (int q = 1; q < 100; ++ q){
   value = value + n;
 }
}

上面 2 个方法，都属于 O(1) 的时间复杂度。calB() 虽然内部包含了一个 for 循环，但是循环次数为固定值 100，依然属于常数阶。

2.2 解题

前面也提到，这道题的难点在于，如何处理 setAllValue() 的逻辑，让其能保证 O(1) 的时间复杂度，同时还影响所有 index 在 getValue() 的取值。

假设我们这里使用 Array 扩展实现，肯定不能遍历 Array 来修改每个 index 的值，这样就的时间复杂度就降低为 O(n) 了，这不符合题目要求。

这道题完全是一个技巧题，想明白了其实很简单。

建

议

各

位

自

己

先

思

考

一

下

再

继

续

阅

读

技巧就是：引入操作版本号的概念，或者叫操作年龄的概念。

我们可以在每个 index 存储的数据 Entity 上增加一个版本号 age，用于记录当前 Entity 的操作 age。同时再给整个数据结构，增加一个 age 版本号字段和 value 字段，用于记录 setAllValue() 的 age 和 value 值。

直接上代码，我们用一个 Entity 类包装 value，扩展 age 的支持。

class OneArray<T> {
  final val COUNT = 1000
  val array = arrayOfNulls<Entity<T>>(COUNT)
  var age = 0
  var value :T? = null

  fun setValue(index: Int, value: T) {
    if (index >= 1000) {
      throw IndexOutOfBoundsException("Index: $index, Size: $COUNT")
    }
    val item = array.getOrNull(index)?:Entity()
    if (item.age < age) {
      item.age = age
    }
    item.value = value
    array.set(index, item)
  }

  fun getValue(index: Int):T? {
    if (index >= 1000) {
      throw IndexOutOfBoundsException("Index: $index, Size: $COUNT")
    }
    val item = array.getOrNull(index)?:Entity()
    if (item.age < age) {
      return value
    }
    return item.value
  }

  fun setAllValue(value: T){
    this.value = value
    this.age++
  }
  
  class Entity<T> {
    var age = 0
    var value :T? = null
  }
}

验证一下效果。

val oneArray = OneArray<Int>()
oneArray.setValue(1, 6)
oneArray.setValue(5, 30)
oneArray.setValue(10, 60)
Log.i("cxmyDev","OneArray#getValue(1) ->${oneArray.getValue(1)}")
Log.i("cxmyDev","OneArray#getValue(5) ->${oneArray.getValue(5)}")
Log.i("cxmyDev","OneArray#getValue(6) ->${oneArray.getValue(6)}")
Log.i("cxmyDev","==========")
oneArray.setValue(5, 20)
Log.i("cxmyDev","OneArray#setValue(5, 20)")
Log.i("cxmyDev","OneArray#getValue(5) ->${oneArray.getValue(5)}")
Log.i("cxmyDev","==========")
oneArray.setAllValue(100)
Log.i("cxmyDev","OneArray#setAllValue(100)")
Log.i("cxmyDev","OneArray#getValue(1) ->${oneArray.getValue(1)}")
Log.i("cxmyDev","OneArray#getValue(5) ->${oneArray.getValue(5)}")
Log.i("cxmyDev","OneArray#getValue(10) ->${oneArray.getValue(10)}")
Log.i("cxmyDev","==========")
oneArray.setValue(5, 200)
Log.i("cxmyDev","OneArray#setValue(5, 200)")
Log.i("cxmyDev","OneArray#getValue(5) ->${oneArray.getValue(5)}")
Log.i("cxmyDev","OneArray#getValue(6) ->${oneArray.getValue(6)}")

Log 输出。

I/cxmyDev: OneArray#getValue(1) ->6
I/cxmyDev: OneArray#getValue(5) ->30
I/cxmyDev: OneArray#getValue(6) ->null
I/cxmyDev: ==========
I/cxmyDev: OneArray#setValue(5, 20)
I/cxmyDev: OneArray#getValue(5) ->20
I/cxmyDev: ==========
I/cxmyDev: OneArray#setAllValue(100)
I/cxmyDev: OneArray#getValue(1) ->100
I/cxmyDev: OneArray#getValue(5) ->100
I/cxmyDev: OneArray#getValue(10) ->100
I/cxmyDev: ==========
I/cxmyDev: OneArray#setValue(5, 200)
I/cxmyDev: OneArray#getValue(5) ->200
I/cxmyDev: OneArray#getValue(6) ->100

可以看到，setAllValue() 符合预期。

2.3 聊聊思路

增加版本号（or age）的设计，其实有很多应用场景，我这里举 2 个例子。

原子类底层依赖 CAS 操作，保证操作的原子性，这个过程是无法识别 ABA 问题的，即值从 A 变为 B 后又改回为 A 了，CAS 本身是无法识别的，在这种场景下，就可以增加操作版本号来解决。

再比如 JVM 的 GC 策略中，分代回收策略的新生代（Young Generation）中，如果触发新生代 GC（MinorGC），对于未被回收的对象，会增加其年龄计数，当计数到达阈值（15）时，会移入老年代管理。

新生代 GC 的年龄技术，虽然不如原子类 ABA 问题贴合本题，但依然说明了版本号（or age）设计的一些使用场景，大家了解一下即可，好的设计总是相通的。

三、小结

今天聊了一个操作为 O(1) 的时间复杂度的数据结构的设计，这种问题其实很依赖技巧，多看案例多思考才是解药。

在这个设计中，引入了版本号（or age）的概念，维护了对 allValue 的操作，以此实现 O(1) 复杂度的操作。

-- End --

本文对你有帮助吗？留言、转发、点好看是最大的支持，谢谢！

推荐阅读：