我有一个算法问题,我在工作中遇到但未能提出一个令人满意的解决方案.我浏览了这个论坛一些,最接近我遇到同样的问题是如何在一个混洗的连续整数数组中找到一个重复的元素？.
我有一个N个整数元素的列表,它可以包含元素1-M(M> N),进一步列表是未排序的.我想要一个将此列表作为输入的函数,并返回列表中不存在的1-M范围内的值.该列表不包含重复项.我希望有一个o(N)解决方案,没有使用额外的空间UPDATE:函数无法更改原始列表L.
例如N = 5 M = 10列表(L):1,2,4,8,3然后f(L)= 5说实话我不在乎它是否返回5以外的元素,只要它满足以上的约束
到目前为止,我提出的唯一解决方案是使用额外的M元素数组.遍历输入列表并将相应的数组元素设置为1(如果列表中存在).然后再次遍历此列表并返回值为0的第一个元素的索引.如您所见,这会使用额外的o(M)空间并具有复杂度2*o(N).任何帮助我们都会感激.
感谢大家的帮助.堆栈溢出社区绝对是非常有用的.为每个人提供一些我正在努力解决的问题的背景.我有一组M令牌,我给一些客户(每个客户一个).当客户完成令牌后,他们就会回到我的堆里.正如您所看到的那样,我给客户端一个令牌进行排序.
所以M = 3令牌
client1:1 <2,3>
client2:2 <3>
client1返回:1 <1,3>
客户端3:3 <1>
现在问题是给client4令牌1.我可以在这个阶段给出客户端4令牌2并对列表进行排序.不确定这是否有帮助.在任何情况下,如果我想出一个很好的清洁解决方案,我一定会发布它
只是意识到我可能会困扰每个人.我被叫时,我没有免费令牌列表.我可以静态地维护这样的列表,但我宁愿不这样做
你可以拥有 O(N) 的时间和空间。您可以确定 1..N+1 内不存在元素，因此创建一个包含 N+1 个元素的数组，并忽略大于 N+1 的数字。
如果 M 比 N 大，假设 M>2N，则在 1..M 中生成一个随机数，并在 O(N) 时间、O(1) 空间中检查它是否不在列表中。在单遍中找到解决方案的概率至少为 1/2，因此（几何分布）预期的遍数是恒定的，平均复杂度为 O(N)。
如果 M 是 N+1 或 N+2，请使用此处描述的方法。