c++ - 如何在恒定时间内减少数组的内容？

Question

在学习 C++ 数据结构时，我在想是否可以将整数数组的内容减少一个整数但在恒定时间内。如果我有足够的内存，我该怎么做？

Answer 1

如果我理解正确，没有例子真的很难。

您必须遍历元素以降低它们的值。如果不在 O(n) 时间内迭代它们，它们就无法访问每个值。

话虽如此，如果您将数组中的每个值都减少相同的值，那么您可以使用惰性方法并将减少量存储在单独的变量中，然后当用户想要查看元素的值时，只需将其减少存储量。

Answer 2

我想这std::vector::resize就是你要找的。假设您有一个包含 10 个元素的向量，并且您想将此大小减小 6 以仅包含 4 个元素，那么您可以这样做：

int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> v(a, a + 10);
// v contains 10 elements here
v.resize(v.size() - 6);
// v contains 4 elements here

如果发生重新分配（当必须获得更大的内存块时） ，复杂度是O(n)，但如果向量只是缩小，它应该是O(1)

Answer 3

您希望从数组的每个元素中减去一个值 m。

为了实现这一点，您显然需要访问数组中的每个元素。这意味着 O(n) 是该任务复杂性的下限。它不可能在恒定时间内完成。