我有一个算法问题,我在工作中遇到但未能提出一个令人满意的解决方案.我浏览了这个论坛一些,最接近我遇到同样的问题是如何在一个混洗的连续整数数组中找到一个重复的元素？.
我有一个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并对列表进行排序.不确定这是否有帮助.在任何情况下,如果我想出一个很好的清洁解决方案,我一定会发布它
只是意识到我可能会困扰每个人.我被叫时,我没有免费令牌列表.我可以静态地维护这样的列表,但我宁愿不这样做
这是我想要做的.我有两个元组列表.构建一个元素列表,使list1中元组中的第一个元素与列表2中元组中的第一个元素匹配
list1 = [('a', 2), ('b', 3), ('z', 5)]
list2 = [('a', 1), ('b', 2), ('c', 3)]
list3 = ['a','b']
注意:第一个元素不能重复
在查看了python列表推导之后,这就是我所做的
[x[0] for x in list1 if (x[0] in [y[0] for y in list2])]
我的问题是,这是一个有经验的python程序员如何编写这个代码？自己编写了这个,我仍然觉得这很难读.如果不是,你会怎么做呢