O(1) space 中 -n 到 n 范围内的列表的第一个重复值
first duplicate value for a list in range -n to n in O(1) space
我最近在解决一个问题。问题只是询问以下内容，
给定范围为 1 到 n 的整数列表，找到列表中的第一个重复值，
现在显而易见的解决方案是使用哈希 table 并在 O(n) space 和 O(n) 时间内完成，但我发现有一个巧妙的技巧我们可以可以用 O(1) space.
来解决
我们可以只迭代数组，然后对于a[i]，我们将索引a[a[i]]标记为负数，然后我们检查之前是否有任何整数为负数，如果是，这是第一个重复值。
我的问题是，如果数组中也有负值怎么办？有解决这个问题的通用方法吗？
存储数组本身是 O(n) space 的复杂度。如果您关心使用额外的 space，您所做的就是使用负值作为 1 位存储的标志，这会将您可以存储的值的范围减少 1 位。您可以想出任意数量的方案来在某处存储一个额外的标志位：例如，处理 int_min/2 和 int_max/2 之间的值，您可以将所有值向上移动为非负值，然后使用符号位，但在实际应用中不值得，除非您的内存受到严重限制。对于真正的大数据操作，您甚至无法存储整个数组，您可以使用概率在线方法，例如 count-min sketch。
what if we have negative values as well in the array?
如果你的意思是值在 −+1... 或 −...−1,... 范围内，使得可能值的计数为 2，那么你可以保留 2 位而不是 1 位用于在数组中放置标志：一个用于当值为正时，一个用于当值为负时，或者您想要将值范围一分为二的任何一种方式。
在您的解决方案中，您使用了符号位，在 32 位整数中通常是最左边的位，或者 32nd 位，因此您可以决定保留31st 位作为第二个标志。这意味着不应大于 230−1.
我最近在解决一个问题。问题只是询问以下内容， 给定范围为 1 到 n 的整数列表，找到列表中的第一个重复值，
现在显而易见的解决方案是使用哈希 table 并在 O(n) space 和 O(n) 时间内完成，但我发现有一个巧妙的技巧我们可以可以用 O(1) space.
来解决我们可以只迭代数组，然后对于a[i]，我们将索引a[a[i]]标记为负数，然后我们检查之前是否有任何整数为负数，如果是，这是第一个重复值。
我的问题是，如果数组中也有负值怎么办？有解决这个问题的通用方法吗？
存储数组本身是 O(n) space 的复杂度。如果您关心使用额外的 space，您所做的就是使用负值作为 1 位存储的标志，这会将您可以存储的值的范围减少 1 位。您可以想出任意数量的方案来在某处存储一个额外的标志位：例如，处理 int_min/2 和 int_max/2 之间的值，您可以将所有值向上移动为非负值，然后使用符号位，但在实际应用中不值得，除非您的内存受到严重限制。对于真正的大数据操作，您甚至无法存储整个数组，您可以使用概率在线方法，例如 count-min sketch。
what if we have negative values as well in the array?
如果你的意思是值在 −+1... 或 −...−1,... 范围内，使得可能值的计数为 2，那么你可以保留 2 位而不是 1 位用于在数组中放置标志：一个用于当值为正时，一个用于当值为负时，或者您想要将值范围一分为二的任何一种方式。
在您的解决方案中，您使用了符号位，在 32 位整数中通常是最左边的位，或者 32nd 位，因此您可以决定保留31st 位作为第二个标志。这意味着不应大于 230−1.