给出2个排序数字列表,如下所示:
>>> list1 = list(map(int, '7 22 34 49 56 62 76 82 89 161 174'.split()))
>>> list2 = list(map(int, '7 14 49 57 66 76 135 142 161'.split()))
你知道吗努皮因德将产生7、49、76和161的真值。你知道吗
但我愿意接受一个特定的公差,即最多3,并为7、49、57、76和161生成真值(因为列表1中的56和列表2中的57只相差1)
我编写了以下代码来生成所需的结果,其中FifoList()是fifo堆栈的实现:
class FifoList:
def __init__(self):
self.data = []
def append(self, data):
self.data.append(data)
def pop(self):
return self.data.pop(0)
def match_approximate(a, b, approx=3):
c = []
bEnd = False
bfifo = FifoList()
for i in b:
bfifo.append(i)
y = 0
for x in a:
if bEnd:
continue
while True:
if y == 0 or x - y > approx:
try:
y = bfifo.pop()
except KeyError:
bEnd = True
break
if abs(x - y) <= approx:
c.append(y)
break
if y > x:
break
return c
只是想知道是否有其他更好的方法来实现这一点?你知道吗
感谢@MattMessersmith,我已经实现了我的最终解决方案,它满足了2个需求:
在两个彼此接近的列表中匹配项
代码如下:
我不知道你为什么在这里排队。它似乎不是解决这个问题的正确数据结构。此外,Python有一个内置的队列数据结构(
collections.deque
,只使用popleft()
而不是pop(0)
)。你知道吗一种更简单的方法(imo)是只维护指向每个数组的“指针”(或索引),从开始处开始。如果元素彼此在
approx
范围内,则添加它们,并递增两个指针。如果a
的元素小于b
的元素,则增加a
的指针。否则,增加b
的指针。继续,直到两个指针都用完(即指向列表的末尾)。它以O(N),线性时间运行。下面是上述算法的实现:跑步
将输出
[5, 6, 7, 49, 57, 76, 161, 163]
(这是我假设所期望的,但是请参见下面关于一些不清楚的边缘情况的内容)。如果您在当前impl上运行这个案例,您将得到一个IndexError
。你知道吗在某些边缘情况下,我们还不完全清楚该怎么办:
当你有一个近似匹配时,你会在结果中添加哪个元素?这个impl只是拉入
b
的元素(如示例所示)。应如何处理重复项?在这个impl中,如果两个列表都包含一个dup,它将被添加两次。如果只有一个列表包含重复项,则只添加一次元素。关于dup的一个更复杂的例子是理解如果我们有
[4,5]
和[4,5]
作为输入,那么我们的输出应该是[4,5]
还是[4,4,5,5]
(因为4
和5
都在approx
之内,4
也与5
匹配)。绑定的
approx
是包含的还是独占的(即<= approx
或< approx
)?请随意调整上述impl,以处理您认为在这些情况下需要执行的任何操作。你知道吗
嗯。你知道吗
从X中选取近似匹配:
输出:
从Y中选取近似匹配:
输出:
相关问题 更多 >
编程相关推荐