数组作业问题
给你一个整数在1到1000000之间的数组。 一个整数在数组中两次。 你怎么能确定哪一个？ 你能想出一个方法来做一点点额外的记忆。
ALGO：
- 解决scheme1：
- 有一个哈希表
- 遍历数组并将其元素存储在散列表中
- 只要你find一个已经在哈希表中的元素，它就是dup元素
- 优点：
- 它运行在O（n）时间，只有一次通过
- 它使用O（n）额外的内存
缺点：
- 使用合并sorting（O（nlogn）时间）对数组进行sorting
- 再次parsing，如果你看到一个元素两次，你有dup。
- 优点：
- 它不使用额外的内存
- 运行时间大于O（n）
缺点：
你们能想出更好的解决scheme吗？
这个问题有点模棱两可。 当请求是“哪一个”时，是指返回重复的值 ，还是重复序列中的位置 ？ 如果前者，以下三种解决scheme中的任何一种都可以工作; 如果是后者，第一个是唯一有帮助的。
解决scheme＃1：假定数组是不可变的
build立一个位图; 在迭代数组的时候设置第n位。 如果这个位已经被设置，你已经find了一个重复的。 它运行在线性时间，并将适用于任何大小的数组。
位图将会创build与数组中可能的值一样多的位。 在遍历数组时，您检查数组中的第n位。 如果已设置，则已find您的副本。 如果不是，那就设置它。 （这样做的逻辑可以在位数组的维基百科条目中的伪代码中看到，也可以使用System.Collections.BitArray类。）
解决scheme2：假定数组是可变的
对数组进行sorting，然后进行线性search，直到当前值等于先前的值。 使用最less的记忆。 加分点改变sortingalgorithm以在比较操作期间检测到重复并提前终止。
解决scheme＃3 :(假定数组长度= 1,000,001）
- 总结数组中的所有整数。
- 从中减去1到1000000（含）的整数。
- 剩下的将是你的重复价值。
这几乎不需要额外的内存，如果你同时计算总和，可以一次完成。
缺点是你需要做整个循环才能find答案。
其优点是简单，实际上运行速度比其他解决scheme高。
假设所有从1到1,000,000的数字都在数组中 ，所有数字的总和为1到1,000,000是(1,000,000)*(1,000,000 + 1)/2 = 500,000 * 1,000,001 = 500,000,500,000 。
所以把数组中的所有数字加起来，减去500,000,500,000，然后你会留下两次出现的数字。
O（n）时间和O（1）存储器。
如果假设不成立 ，可以尝试使用Bloom Filter–它们可以比散列表更紧凑地存储（因为它们只存储存在的事实），但是它们确实存在误报的风险。 这个风险可以通过我们select花费在Bloomfilter上的内存来决定。
然后，我们可以使用布隆filter来检测O（n）时间中潜在的重复，并在O（n）时间内检查每个候选者。
这个python代码是QuickSort的修改 ：
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）中find重复的，我想。 它在堆栈上使用额外的内存，但是它可以被重写为只使用原始数据的一个副本，我相信：
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)
产生越来越 小的列表parsing会通过调用pop（）来破坏原始数据。 如果arr在删除越来越 小之后不是空的，那么必须有一个重复的并且必须是枢轴的 。
代码遭受sorting数据通常的堆栈溢出问题，所以无论是随机数据还是迭代解决scheme都是必要的：
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
但是，现在代码需要在循环顶部对数据进行深层复制，从而改变内存需求。
这么多的计算机科学。 天真algorithm在python中将我的代码封装起来，可能是因为python的sortingalgorithm：
def findDuplicate(arr): arr = sorted(arr) prev = arr.pop(0) for element in arr: if element == prev: return prev else: prev = element return None
我不build议对数组进行sorting然后检查，而是build议编写一个比较sorting函数的实现，只要finddup就退出，导致没有额外的内存要求（显然取决于您select的algorithm），最坏的情况O（nlogn）时间（同样取决于algorithm），而不是最好的（和平均值，取决于…）情况O（nlogn）时间。
例如就地合并sorting的实现。
提示：使用A XOR A == 0和0 XOR A == A的属性
作为解决scheme（2）的一个变体，您可以使用基数sorting 。 没有额外的内存，并将运行在线性时间。 你可以争辩说时间也受到数字表示的大小的影响，但是你已经给出了这样的界限：基数sorting在时间O（kn）中运行，其中k是你可以对每一次传递进行sorting的数字的数量。 这使得整个algorithmO（7n）的sorting加上O（n）来检查重复的数字 – O（8n）= O（n）。
优点：
- 没有额外的记忆
- 上）
缺点：
- 需要八个O（n）通行证。
而如何find所有重复的问题？ 这可以在小于O（n ln n）的时间内完成吗？ （sorting和扫描）（如果你想恢复原始数组，在结束之后进行原始索引和重新sorting，这可以在O（n）时间完成）
def singleton(array): return reduce(lambda x,y:x^y, array)
sorting整数sorting他们应该是他们的地方。 如果你发现“碰撞”，比find正确的号码。
空间复杂度O（1）（只能覆盖相同的空间）时间复杂度小于O（n），因为你会统计发现碰撞在结束之前。
