作为一道作业问题，给出了以下任务：
你有一个包含1到1,000,000之间整数的数组。其中一个整数在数组中出现了两次。你如何确定这个整数？你能想到一种使用较少额外内存的方法吗？
我目前的解决方案：
优点
它运行时间为O(n)，并且只需一次遍历
缺点
它使用O(n)的额外内存
优点
它不使用额外内存
缺点
运行时间大于O(n)
你们能想到更好的解决方案吗？
这个问题有点含糊不清：当请求是“哪一个”时，它是指返回重复的值还是重复的位置？如果是前者，则以下任何一种解决方案都可以；如果是后者，则第一种解决方案是唯一能帮助你的。
构建一个位图；在迭代数组时设置第n 个位。如果该位已经设置，则已找到重复项。它在线性时间内运行，并适用于任何大小的数组。
位图将创建与数组中可能值相同的位数。在遍历数组时，检查数组中的n 个位。如果设置了它，则已找到重复项。如果没有，那么设置它。（执行此操作的逻辑可以在维基百科上看到的这篇文章的伪代码中看到位数组（Bit arrays）或使用System.Collections.BitArray类。）
对数组进行排序，然后进行线性搜索，直到当前值等于前一个值。使用所有解决方案中最少的内存。将排序算法改为在比较操作期间检测重复项并尽早终止，可获得额外的奖励分数。
这几乎不需要额外的内存，如果同时计算总和，则可以一次性完成。
缺点是需要完整地循环以找到答案。
优点是简单易用，且很可能比其他解决方案运行更快。
这段Python代码是快速排序的修改版：
def findDuplicate(arr):
orig_len = len(arr)
if orig_len <= 1:
return None
pivot = arr.pop(0)
greater = [i for i in arr if i > pivot]
lesser = [i for i in arr if i < pivot]
if len(greater) + len(lesser) != orig_len - 1:
return pivot
else:
return findDuplicate(lesser) or findDuplicate(greater)
我认为它可以在O(n logn)的时间内找到重复项。它使用了堆栈上的额外内存，但我相信它可以重新编写以仅使用原始数据的一份副本：
def findDuplicate(arr):
orig_len = len(arr)
if orig_len <= 1:
return None
pivot = arr.pop(0)
greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot]
lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot]
if len(arr):
return pivot
else:
return findDuplicate(lesser) or findDuplicate(greater)
产生 greater 和 lesser 的列表推导式通过调用pop()破坏了原始数据。如果从中删除greater和lesser后，arr不为空，则必须存在重复项，且重复项为pivot。
对于排序数据，代码会出现常见的堆栈溢出问题，因此需要使用随机枢轴或迭代解决方案将数据排队：
def findDuplicate(full):
import copy
q = [full]
while len(q):
arr = copy.copy(q.pop(0))
orig_len = len(arr)
if orig_len > 1:
pivot = arr.pop(0)
greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot]
lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot]
if len(arr):
return pivot
else:
q.append(greater)
q.append(lesser)
return None
然而，现在代码需要在循环的顶部进行数据的深度复制，这会改变内存需求。
计算机科学就到此为止。Python中的排序算法可能导致我的代码被朴素算法覆盖：
def findDuplicate(arr):
arr = sorted(arr)
prev = arr.pop(0)
for element in arr:
if element == prev:
return prev
else:
prev = element
return None
def singleton(array):
return reduce(lambda x,y:x^y, array)
优点：
缺点：
通过将整数排序到它们应该在的位置上来对整数进行排序。如果出现“冲突”，那么你就找到了正确的数字。
空间复杂度为O(1)（只是可以被覆盖的相同空间） 时间复杂度小于O(n)，因为你会在到达末尾之前统计出冲突。