在O（1）中创建一个长度为n的数组，除索引匹配特定条件的一个值外，还用0初始化所有值？

Question

我想创建一个长度为n的数字类型的数组。数组中的所有值都应为0，但索引匹配条件的值除外。

这就是我目前的做法：

const data: number[] = [];
for (let i = 0; i < n; i++) {
  if (i === someIndex) {
    data.push(someNumber);
  } else {
    data.push(0);
  }
}

所以可以说n = 4，someIndex = 2，someNumber = 4将导致数组[0, 0, 4, 0]。

是否可以用O（1）代替O（n）？

Answer 1

您需要分配n个值，因此需要做大量的工作。功随n的增加而线性增加。

话虽如此，您希望通过使用.fill使您的代码更快一点：

const data: number[] = Array(n).fill(0);
data[someIndex] = someNumber;
但是请不要误会；这仍然是[[O（n）

：.fill可能更快，但是仍然需要用零填充整个数组，这意味着需要初始化相应的内存大小，因此操作具有线性时间复杂度。但是，如果您放弃了需要分配零的要求，那么您可以

仅

存储someNumber：

const data: number[] = Array(n);
data[someIndex] = someNumber;

这样，您实际上不会为整个数组分配内存，因此此代码段在恒定时间内运行。对不同于someIndex的索引的任何访问都将为您提供undefined的值。您可以捕获该条件并将其即时转换为零：

let value = i in data ? data[i] : 0;

显然，如果您要像这样访问数组的[[all

索引，您将再次具有线性时间复杂度。

Answer 2