从一个包含1000个元素的数组中生成一个新元素。

Question

我在面试中被问到了这个问题。考虑打孔卡片的情况，每个打孔卡都有64位模式。我建议将每个卡片视为一个int，因为每个int是一组位。

此外，需要考虑到我已经有一个包含1000张这样的卡片的数组。我必须每次生成一个新元素，该元素与之前的1000张卡片不同。数组中的整数（也称为卡片）不一定按顺序排列。

更重要的是，如果问题是针对C++的，那么64位int从哪里来，以及如何从数组中生成这张新卡片，使其与数组中已有的所有元素都不同呢？

- Cipher

---

也许我误解了。每个新生成的数字都必须与所有以前的数字不同吗？还是每次都删除第一个元素？如果是这样，那么可以轻松地制定一个O(1000) = O(1)的解决方案。 - Fred Foo

@larsmans：要求新生成的整数与之前所有的整数都不同。 - Cipher

相关问题：在给定的40亿个整数中找到一个不在其中的整数 - Christian Ammer

Answer 1

有2的64次方个64位整数，这个数字比1000还大得多，最简单的解决方法是生成一个随机的64位数字，并验证它是否在已生成数字的表中（即使它出现的概率非常小，但你最好确定一下）。

由于大部分随机数生成器不会生成64位值，因此你只能编写自己的随机数生成器，或者（更简单的方法）将值合并，例如通过生成8个随机字节，然后将它们memcpy到一个uint64_t中。

至于验证数字是否已经存在，对于一个或两个新数字来说，std::find就足够了；如果你需要查找很多数字，那么对表进行排序并使用二分查找会很值得。或者使用某种类型的哈希表。

- James Kanze

---

但是在已排序的表中插入新元素需要 O(n) 时间，就像 std::find 一样，所以在这两种情况下生成的时间都是 O(n)。 - Fred Foo

@larsmans 但是，具有非常小的常数因子和良好局部性的O(n)经常击败具有大量常数因子和坏局部性的O(lg n)。 - James Kanze

@James 在大量操作中，1000并不算太小。lg 1000等于10，因此在O(n)能与O(lg N)竞争之前，您必须有相当大的常数。 - flight

@quasiverse 请记住，O(n)仅适用于插入操作，而不是查找操作。向map中插入元素需要进行分配，这可能会对常数因子产生非常大的影响。(当然，如果性能真的成为问题，还有更好的解决方案可用。但它们更加复杂，因此更容易出错。) - James Kanze

Answer 2

我可能有所遗漏，但是其他大部分答案对我来说过于复杂。只需对原始数组进行排序，然后从零开始计数：如果当前计数在数组中，则跳过它，否则你就得到了下一个数字。这个算法的时间复杂度为O(n)，其中n是新生成数字的数量：排序数组和跳过现有数字都是常量。以下是一个例子：

#include <algorithm>
#include <iostream>
unsigned array[] = { 98, 1, 24, 66, 20, 70, 6, 33, 5, 41 };

unsigned count = 0;
unsigned index = 0;

int main() {
  std::sort(array, array + 10);
  while ( count < 100 ) {
    if ( count > array[index] )
      ++index;
    else {
      if ( count < array[index] )
        std::cout << count << std::endl;
      ++count;
    }
  }
}

- Nicola Musatti

---

过于复杂？也许是。前几张卡更快吗？绝对是。 - Mooing Duck

@Mooing Duck：当然，但是为什么要编写不存在的需求代码呢？OP提到“每次都是新数字...”，没有明确的性能要求，也没有指示将提取多少个数字。实际上，即使只是将每个64位无符号数字与数组中的所有元素进行比较，对于大多数目的来说，速度已经足够快了。 - Nicola Musatti

我编写代码时更多地是按照自己的理解来实现他们想要的，因为他们说的往往不完全是他们想要的。我曾经有一次作业任务，需要编写一个函数，如果字符串参数大于5个字符，则返回true。符合规格的答案是：bool IsGreatFive(const char*) {return true;}。 - Mooing Duck

Answer 3

这里有一个时间复杂度为O(n)的算法:

int64 generateNewValue(list_of_cards)
{
    return find_max(list_of_cards)+1;
}

注意：正如@amit在下面指出的那样，如果INT64_MAX已经在列表中，这个方法将会失败。

就我所知，这是你唯一可以得到O(n)时间复杂度的方法。如果你想要处理这个（相当重要的）边缘情况，那么你必须进行一些适当的排序或搜索，这将使你的时间复杂度达到O(n log n)。

- Oliver Charlesworth

---

O(n^2)的最坏情况，确实相当慢 :| - amit

@Oli：我当然考虑过这个问题，但是由于一遍又一遍地循环1000个元素肯定不是一个好的预期答案，所以我没有给出这个答案。 - Cipher

如果列表中同时包含max==MAX_INT_64和MIN_INT_64，那么这个[更新的解决方案]将会失败。 - amit

@Chris：这个需求是要生成一个新元素。将其附加到列表中可以轻松实现，如下所示：list_of_cards.append(generateNewValue(list_of_cards))。 - Oliver Charlesworth

@Oli：如果该函数跟踪一个“最大值”，并发现使用的最大值小于“最大值-1”，那么如果MAX_INT_64在列表中，它就不会失败。这更加复杂，但最终可以返回所有数字。 - Mooing Duck

Answer 4

@arne 已经接近成功了。你需要的是一个 自平衡 区间树，它可以在 O(n lg n) 的时间内构建。

然后取出顶部节点，它将存储一些区间 [i, j]。由于区间树的属性，除非 i = UINT64_MIN 或者 j = UINT64_MAX，否则 i-1 和 j+1 都是新键的有效候选项。如果两个都为真，则已经存储了 2^64 个元素，无法生成新元素。存储新元素，最坏情况下需要 O(lg n) 的时间。

即：init操作的时间复杂度为O(nlogn)，generate操作的时间复杂度为O(logn)。这两个操作都是最坏情况下的时间复杂度。这种方法最棒的地方在于顶部节点将会不断“增长”（存储更大的区间）并与其前驱或后继合并，因此树实际上会在内存使用方面缩小，并且最终每个操作的时间复杂度将衰减到O(1)。您也不会浪费任何数字，因此您可以一直生成，直到获得2^64个数字为止。

- Fred Foo

---

好的！这应该比我的树快得多，特别是当现有元素的数量增长时。+1 - arne

你应该能够从一个已排序的std::deque范围中获得更好的性能，而不是从树中获取。稍微复杂一些，但局部性更好（更快），内存更少（更快），无需平衡（更快），并且之后的生成是O(1)。但“范围”概念是一个很棒的想法。 - Mooing Duck

我刚意识到，范围概念也使得返回_任何_未使用的随机数变得微不足道，不像其他方式那样递增/递减。(它们不会均匀分布，并且在生成大量数字之前，这将极大地增加内存使用量) - Mooing Duck

忘记了std::deque的O(n)插入，所以除非你只想在开头和结尾生成数字，否则不要考虑它。 - Mooing Duck

Answer 5

该算法的初始化时间复杂度为O(N lg N)，查询时间复杂度为O(1)，内存使用量为O(N)。我假设您有一些整数类型，我将其称为int64，它可以表示整数[0，int64_max]。

1. 对数字进行排序
2. 创建包含区间[u，v]的链表
3. 插入[1，第一个数字-1]
4. 对于剩余的每个数字，插入[上一个数字+1，当前数字-1]
5. 插入[最后一个数字+1，int64_max]

现在您拥有一个代表未使用的数字的列表。您可以简单地迭代它们以生成新数字。

- flight

---

“排序数字”意味着至少需要 O(lg n) 的临时空间（或 O(n²) 的时间）。区间的链表需要 O(n) 的空间。但是，生成操作确实只需要 O(1) 的时间。 - Fred Foo

@larsmans 不，因为N被固定为1000...但我确实说过排序需要O(N lg N)的时间。也许我有双重标准...那我会编辑一下。 - flight

Answer 6

bool seen[1001] = { false };
for each element of the original array
    if the element is in the range 0..1000
        seen[element] = true
find the index for the first false value in seen

- Keith Thompson

---

是的，那比我的解决方案快，我的解决方案类似，但使用了整数数组。当布尔数组“用完”时，您可以调整范围，以便添加更多值。重置布尔数组将更快（memset），而不是我的循环再次填充增量值。此外，我的设计有一个致命缺陷，因为我使用列表中的第一个值作为“无效”标志，所以它不应包括在失效扫描中。不过，我们都想到了从0开始工作并逐步递增的想法。 - Martin James

Answer 7

将它们全部放入大小 > 1000 的哈希表中，并找到空单元格（这是停车问题）。为此生成一个密钥。当然，这对于较大的表格尺寸效果更好。表格仅需要1位条目。

编辑：这是鸽巢原理。 为哈希函数需要“模表大小”（或其他“半可逆”函数）。

unsigned hashtab[1001] = {0,};
unsigned long long long long numbers[1000] = { ... };

void init (void)
{
unsigned idx;

for (idx=0; idx < 1000; idx++) {
    hashtab [ numbers[idx] % 1001 ] += 1; }

}

unsigned long long long long generate(void)
{
unsigned idx;

for (idx = 0; idx < 1001; idx++) {
    if ( !hashtab [ idx] ) break;  }

return idx + rand() * 1001;
}

- wildplasser

---

哎呀，我看到我刚刚重新发明了Keith Thompson的方法。 - wildplasser

Answer 8

我认为使用某种哈希方式是可行的。因此，您可以根据MOD操作将卡片存储在一些桶中。除非您创建某种索引，否则只能循环整个数组。

如果您查看Java中HashSet的实现，您可能会得到一些线索。

编辑：我假设您希望它们是随机数，如果您不介意序列MAX+1，则以下是一个好的解决方案 :)

- Jan Zyka

---

那么，如果操作者想在哈希表中查找一个不存在的元素，该怎么办呢？ - Fred Foo

你需要生成一个数字，从哈希函数中获取结果，并确定卡片是否已经存在，你需要搜索单个桶而不是整个数组。 - Jan Zyka

我发现很难估计这个操作的预期时间，但查找的最坏情况已经是O(n)（当所有整数恰好映射到相同的哈希值时）。 - Fred Foo

这就是哈希函数的工作原理，对吧 :) 在最坏情况下，时间复杂度可能达到O（n），但如果你的卡片是随机数，这种情况通常不会发生。你可以争论说，在最坏情况下，你永远找不到新卡片，因为你的随机数生成器总是返回“5”，而且已经有了“5”，所以你被卡住了。请注意，我假设（如我的答案中所提到的）他应该选择一个还未在列表中的新卡片 - 因此，任务实际上是：“我有一个随机数。这已经在我的集合中了吗？” - Jan Zyka

这种方法的时间复杂度从预期的O(1)变为预期的O(n)，并且随着表格的增长，需要Theta(n)的内存。我的方法的最坏情况时间复杂度为O(lg n)，但预期时间和内存复杂度都是O(1)。不过在某些情况下，你的方法可能更快，因此需要根据应用程序进行权衡。 - Fred Foo

Answer 9

你可以构建一个二叉树，将已有的元素放入其中，并遍历该树，直到找到深度不为64且子节点少于两个的节点。然后，你可以构造一个“缺失”的子节点并添加一个新元素。这应该相当快，如果我没记错的话，时间复杂度大约是O(n)。

- arne

---

构建包含 n 个元素的二叉树需要 O(n lg n) 的时间。此外，一个节点拥有 <2 个子节点并不表示整数范围中存在间隙。 - Fred Foo

构建平衡二叉树的时间复杂度不是O(n)。 - Oliver Charlesworth

只是想提一下，他得到的数字没有排序并不意味着他不能自己排序。 - RedX

如何构建一个新的子节点，同时确保它是唯一的？ - Oliver Charlesworth

这是一棵二叉树，使用整数的位作为节点值。因此，如果我们找到一个深度为63且只有一个子节点（例如，值为0）的节点a，我们可以通过将1附加到到达节点a的路径的位表示来创建新的子节点。如果我们已经以这种方式生成的数字，则该叶子节点已经存在。这与最初的假设相矛盾，即该叶子节点不存在。 - arne

Answer 10

初始化： 不要对列表进行排序。 创建一个新的长度为1000的数组，包含0..999。 遍历列表，如果任何数字在0..999范围内，则通过将新数组中的值替换为列表中第一项的值来使其无效。

插入： 使用递增索引到新数组。如果该索引处的新数组中的值不是列表中的第一个元素的值，则将其添加到列表中，否则检查新数组中下一个位置的值。 当新数组用完时，使用1000..1999重新填充它，并像上面那样使现有值无效。是的，这是在列表上循环，但不必为每个插入执行此操作。

近似O(1)，直到列表变得非常大，以至于偶尔迭代它以使“新”新数组无效变得显着。也许您可以通过使用一个增长的新数组来缓解这种情况，可能始终是列表的大小？

敬礼， 马丁

- Martin James