具有无限输入检测重复

StackOverflow https://stackoverflow.com/questions/2279568

题

什么是找到重复的整数的无限序列的最优化的方式？

即。如果在无限序列的数目“5”出现两次，然后我们将返回“假”第一次和“真”的第二次。

在我们需要的到底是什么人返回“真”，如果出现整数之前和“假”，如果函数接收整数第一次。函数

如果有两种解决方法，一种是空间向和所述第二时间是明智的，然后提两者。 我会写我的答案解决方案，但我不认为这是最优的。

编辑：请不要假定简单的情形（即不重复，不断上升的序列）。我感兴趣的是如何减少不平凡的案件的空间复杂度（与重复的随机数字）。

有帮助吗？

解决方案

我会使用以下方法：

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

如果n是从开始到重复序列中的元素的数量，则这仅需要O（n）的时间和空间。时间复杂度是最优的，因为你需要至少读取输入序列的元素，直到重复点。

如何序列的长，我们谈论（重复发生之前）？被重复甚至根本保障？对于极端情况下的空间复杂度可能会成为问题。但是，为了提高它，你可能需要知道您的序列更多的结构信息。

更新：如果序列像你说的很长，很少重复次数，你必须减少对空间的需求，那么你可能（给定的顺序足够的结构信息）能够降低空间成本。

举个例子：假设你知道你的无限序列必须返回适合当前范围内的见证最小 - 最大号数的总体趋势。然后，你最终将有已经被包含在序列中整个区间。在这种情况下，可以通过存储这样的间隔，而不是所有包含在其内的元件节省空间。

其他提示

一个位集合对于int的值（2 ^ 32号）将消耗的512Mb。这可能是确定的，如果该位集被分配给不频繁，足够快以及MEM是可用的。

一种替代是压缩位集的工作最好为稀疏位集。

实际上，如果值的最大数目是无限的，则可以使用任何的无损压缩算法对单色位图。如果你想像一个正方形，至少尽可能多的像素作为可能值的数量，可以映射每个值的像素（少数饶）。然后，你可以代表白色的像素这似乎和黑色为他人，如果空间是溢价使用任何压缩算法（也就是肯定已经研究了问题）

您还可以存储块。最坏的情况是在空间为O（n），你需要的数字出现在他们之间正好1相同的，但对于最坏的情况。一旦更多的数字出现，则存储将减少： 我会写伪代码，我将使用一个列表，但你总是可以使用不同的结构

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
}

这个代码是下面的内容：它存储块的列表。对于添加的每个数字，它遍历列表存储这似乎并没有数的数块。让我用一个例子;我将添加[），以示出这在块号，所述第一数量被包括，最后是not.In它是由布尔appeared取代的伪代码。例如，如果你得到的5,9，6,8，7（以该顺序），你将有每个功能之后的下述序列：

[5,6）

[5,6），[9,10）

[5,7），[9,10）

[5,7），[8,10）

[5,10）

在最后一个值你保持5个数字的块只有2。

返回TRUE

如果该序列是无限的话，会有每个可想到的图案的重复。

如果你想知道什么是序列中的第一位置时，有一个重复的数字是另一回事，但有你的问题，你的榜样之间存在差异。

那么，它似乎很明显，在任何解决方案，我们将需要保存已经出现的数字，所以空间明智的，我们将总是有O（N）最坏的情况，其中N < =与我们的号码类型的字长可能数目（即2 ^ 32为C＃INT） - 此如果序列是真的无限是在长时间内有问题/很少重演

。

有关节能已经出现了，我会用一个哈希表，然后每次检查我收到一个新号码的数字。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top