c++ - 这看起来与旧问题相似但不同。给定一个大小为 n 的数组(允许重复的数字)，找到缺失的 2 个数字

Question

<分区>

Answer 1

如果数据未排序，则无法确保您可以在不查看每个值的情况下找到缺失值。所以，最坏的情况是 O(n) 找到它们。要确定缺少哪些，您可以在 O(1) 中通过计算 n 和 sum(1..n) 的阶乘并将乘积和从总和中减去你遇到的每一项。最后，通过求解 a + b = remaining sum 和 a * b = remaining product，您会知道缺少哪些。这是一种作弊，因为您本质上是在进行初步的 O(n) 计算或具有空间影响的表查找。