请仔细阅读此问题,然后将其作为副本关闭,但如果它是一个诚实的副本,我将很高兴知道它.这是查找列表中多个可能的重复整数中的任何一个的概括.
给定任意一组小号的Ñ不同的整数,任何阵列甲的长度N + 1,其中每个条目取自小号,什么是找到一些(必须有至少一个)重复条目的最佳算法甲？
注意:A中可能有多个重复条目,任何条目都可以重复多次.
正如Nemo指出的那样,平凡的解决方案需要O(1)空间和O(N ^ 2)时间.我正在寻找一种能够在不影响空间的情况下缩短时间的解决方案.确切地说,我正在寻找的解决方案:
编辑:集合S用于确保阵列A至少有一个重复的条目.对于这个问题,不要假设您已将S作为有序集给出.您可以查询小号(布尔返回true是S IN小号和false其他),你可以查询一个(请致电A [1] ),但仅此而已.任何对A或S进行排序的解决方案都超出了空间限制.
这种推广使我对原始问题(具有O(1)空间和O(N)时间)的指针解决方案无效,并且我强加的空间约束使fiver的解决方案(其具有O(N)空间和时间)无效.
这个算法类似于Justin Simon的,但关键是如何有效地使用O(1)空间计算S的中值(或第k个元素).
这是关键算法,随机化:
设置低于等于S的最小元素,高于等于S的最大元素.从S中选择一个随机元素x,它位于较低和较高之间(此成本最多为O(n)预期时间).计算x(O(n)时间)的等级.如果x的秩太低,则将x设置为x(O(n)time)的后继,否则将upper设置为等于x的前任(O(n)time).重复直到下限等于上限.
请注意,每次迭代在期望中花费O(n)并且期望有O(lg n)次迭代,因此预期时间成本为O(n lg n)并且空间使用为O(1),因为我们仅存储较低和较高.
使用这种能力来选择第k个元素,然后我们可以使用原始问题中建议的鸽子原理来找到包含太多元素的S的越来越小的片段,使用O(lg n)线性扫描A和O(1)空间用于存储每个区域中相关的元素总和.除了寻找第k个元素的O(n lg n)成本之外,每个这样的迭代花费O(n),并且存在O(lg n)次迭代,因此总成本是O(n lg ^ 2 n).