1

在无限的整数序列中找到重复的最佳方法是什么？

即如果在无限序列中数字“5”出现两次，那么我们将第一次返回“false”，第二次返回“true”。

最后，我们需要一个函数，如果整数出现在前面，则返回“true”，如果函数第一次收到整数，则返回“false”。

如果有两个解决方案，一个是空间方面的，第二个是时间方面的，那么两者都提到。我会在答案中写下我的解决方案，但我认为这不是最佳解决方案。

编辑：请不要假设微不足道的情况（即没有重复，不断上升的序列）。我感兴趣的是如何降低非平凡案例的空间复杂度（具有重复的随机数）。

4

5 回答 5

1

我会使用以下方法：

使用哈希表作为您的数据结构。对于读取的每个数字，将其存储在您的数据结构中。如果在您发现重复之前它已经存储了。

如果 n 是从开始到重复的序列中元素的数量，那么这只需要 O(n) 时间和空间。时间复杂度是最佳的，因为您至少需要读取输入序列的元素直到重复点。

我们正在谈论多长时间的序列（在重复发生之前）？甚至可以保证重复吗？对于极端情况，空间复杂性可能会成为问题。但要改进它，您可能需要了解有关序列的更多结构信息。

更新：如果序列如您所说的非常长且很少重复，并且您必须减少空间需求，那么您可能（在序列上有足够的结构信息）能够减少空间成本。

举个例子：假设您知道您的无限序列一般倾向于返回适合当前见证的最小-最大数字范围内的数字。然后，您最终将拥有已包含在序列中的整个间隔。在这种情况下，您可以通过存储此类间隔而不是其中包含的所有元素来节省空间。

于 2010-02-17T09:47:50.437 回答
1

用于 int 值（2^32 个数字）的 BitSet 将消耗 512Mb。如果 BitSet 不经常分配、足够快并且内存可用，这可能没问题。

另一种方法是最适合稀疏 BitSet 的压缩BitSet。

于 2010-02-17T14:19:12.693 回答
1

实际上，如果值的最大数量是无限的，您可以对单色位图使用任何无损压缩算法。如果您想象一个正方形的像素数至少与可能值的数量一样多，您可以将每个值映射到一个像素（有一些备用）。然后，您可以将白色表示为出现的像素，将黑色表示为其他像素，如果空间非常宝贵，则可以使用任何压缩算法（这当然是一个已经研究过的问题）

您还可以存储块。最坏的情况在空间 O(n) 中是相同的，但对于最坏的情况，您需要出现的数字在它们之间恰好有 1。一旦出现更多数字，存储空间就会减少：我将编写伪代码并使用 List，但您始终可以使用不同的结构

List changes // global

boolean addNumber(int number):
  boolean appeared = false
  it = changes.begin()
  while it.hasNext():
    if it.get() < number:
      appeared != appeared
      it = it.next()
    else if it.get() == number:
      if !appeared: return true
      if it.next().get() == number + 1
        it.next().remove() // Join 2 blocks 
      else 
        it.insertAfter(number + 1)  // Insert split and create 2 blocks
      it.remove()
        return false
    else: // it.get() > number
      if appeared: return true
      it.insertBefore(number)
      if it.get() == number + 1:
        it.remove() // Extend next block
      else:
        it.insertBefore(number + 1)  
  }
  return false
}

这段代码如下：它存储了一个块列表。对于您添加的每个数字，它会遍历存储出现的数字块和未出现的数字的列表。让我用一个例子来说明；我将添加 [) 来说明块中的哪些数字，包含第一个数字，最后一个不包含。在伪代码中它被替换为 boolean appeared。例如，如果您得到 5、9、6、8、7（按此顺序），您将在每个函数之后有以下序列：

[5,6)

[5,6),[9,10)

[5,7),[9,10)

[5,7),[8,10)

[5,10)

在最后一个值中，您保留一个只有 2 个的 5 个数字块。

于 2012-01-28T03:17:27.560 回答
0

返回真

如果序列是无限的，那么每个可以想象的模式都会重复。

如果您想知道的是当有重复数字时序列中的第一位，那是另一回事，但是您的问题和示例之间存在一些差异。

于 2010-02-17T09:52:03.553 回答
0

好吧，似乎很明显，在任何解决方案中，我们都需要保存已经出现的数字，因此在空间方面，我们总是会遇到 O(N) 的最坏情况，其中 N<= 可能的数字以及我们数字的字长类型（即 C# int 的 2^32） - 如果序列真的是无限的/很少重复，这在很长一段时间内都是有问题的。

为了保存已经出现的数字，我会使用哈希表，然后在每次收到新数字时检查它。

于 2010-02-17T09:57:21.670 回答