用无限输入检测重复 [英] Detecting repetition with infinite input

问题描述

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

What is the most optimal way to find repetition in a infinite sequence of integers?

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

i.e. if in the infinite sequence the number '5' appears twice then we will return 'false' the first time and 'true' the second time.

如果函数首次接收到整数，则需要一个返回true的函数，如果整数出现，则返回false。

In the end what we need is a function that returns 'true' if the integer appeared before and 'false' if the function received the integer the first time.

如果有两个解决方案，是空间上的，第二个是时间性的，然后提到两者。
我会在答案中写下我的解决方案，但我不认为这是最佳选择。

If there are two solutions, one is space-wise and the second is time-wise, then mention both. I will write my solution in the answers, but I don't think it is the optimal one.

编辑：请不要假设琐碎的案例（即不重复，不断上升的序列）。我感兴趣的是如何减少非平凡情况的空间复杂性（带重复的随机数）。

edit: Please don't assume the trivial cases (i.e. no repetitions, a constantly rising sequence). What interests me is how to reduce the space complexity of the non-trivial case (random numbers with repetitions).

推荐答案

d使用以下方法：

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

Use a hash table as your datastructure. For every number read, store it in your datastructure. If it's already stored before you found a repetition.

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

If n is the number of elements in the sequence from start to the repetition, then this only requires O(n) time and space. Time complexity is optimal, as you need to at least read the input sequence's elements up to the repetition point.

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

How long of a sequence are we talking (before the repetition occurs)? Is a repetition even guaranteed at all? For extreme cases the space complexity might become problematic. But to improve it you will probably need to know more structural information on your sequence.

更新：如果顺序与您说很久很少重复，您必须减少空间需求，那么你可以（给出足够的结构信息）可以减少空间成本。

Update: If the sequence is as you say very long with seldom repetitions and you have to cut down on the space requirement, then you might (given sufficient structural information on the sequence) be able to cut down the space cost.

作为一个例子：让我们说你知道你的无限序列有一个一般的趋势，返回符合目前最小最大数目的当前范围内的数字。那么你最终将有一个已经包含在序列中的整个间隔。在这种情况下，您可以通过存储这些间隔而不是其中包含的所有元素来节省空间。

As an example: let's say you know that your infinite sequence has a general tendency to return numbers that fit within the current range of witnessed min-max numbers. Then you will eventually have whole intervals that have already been contained in the sequence. In that case you can save space by storing such intervals instead of all the elements contained within it.

这篇关于用无限输入检测重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！