给定两个集合,如何对一个集合中的每个元素与另一个集合中的每个元素进行成对比较。在
我想得到初始集合中每个元素的前3个结果。\
有没有更快的方法来解决这个任务。我正在寻找一种更像Python的任务。在
set1 = set([str(item) for item in range(100)]) # Pls. note originally set contains strings
set2 = set([str(item) for item in range(50,150)]) # set([str(item) for item in range(50,100)])
for item in set1:
max = [-1,-1,-1]
for stuff in set2:
val = magicComp(item,stuff)
if val > max[0]:
max[2] = max[1]
max[1] = max[0]
max[0] = val
elif val > max[1]:
max[2] = max[1]
max[1] = val
elif val > max[2]:
max[2] = val
如果我们想成为真正的Python
应该会成功的。但是,这仍然是O(n²ln n),因为我们需要为每个项目重新排序第二组。在
嗯,快点。对于每个内部迭代,原始版本的时间复杂性为
O(3n)
。在下面是时间复杂度更快的
O(nlg3)
。在你的答案不错,这比在每次迭代时对数组进行排序要好,但仍然是O(N^2)。在
由于您知道所需的数组索引,因此可以使用quickselect算法在O(logn)时间内基于magicComp函数查找索引0,1,2。这将把运行时间减少到O(n*logn)
基于该链接中的代码,您的代码将类似于:
相关问题 更多 >
编程相关推荐