我面临着在数字序列中找到给定长度的不连续性(间隙)的问题。因此,例如,给定[1,2,3,7,8,9,10]
和 的差距length=3
,我会找到[4,5,6]
。如果差距是length=4
,我什么也找不到。当然,真正的序列要长得多。我在很多帖子中都看到了这个问题,它有各种应用程序和可能的实现。
我认为可能有效并且应该相对较快的一种方法是将完整集表示为一个位数组,其中包含 1 表示可用数字和 0 表示缺失 - 所以上面看起来像[1,1,1,0,0,0,1,1,1,1]
。然后可能运行一个窗口函数,它将用完整的集合对给定长度的数组进行 XOR 掩码,直到所有位置的结果为 1。这将需要在大约 ~O(n) 内对整个序列进行单次传递,加上成本在每次运行中进行掩蔽。
这是我设法想出的:
def find_gap(array, start=0, length=10):
"""
array: assumed to be of length MAX_NUMBER and contain 0 or 1
if the value is actually present
start: indicates what value to start looking from
length: what the length the gap should be
"""
# create the bitmask to check against
mask = ''.join( [1] * length )
# convert the input 0/1 mapping to bit string
# e.g - [1,0,1,0] -> '1010'
bits =''.join( [ str(val) for val in array ] )
for i in xrange(start, len(bits) - length):
# find where the next gap begins
if bits[i] != '0': continue
# gap was found, extract segment of size 'length', compare w/ mask
if (i + length < len(bits)):
segment = bits[i:i+length]
# use XOR between binary masks
result = bin( int(mask, 2) ^ int(segment, 2) )
# if mask == result in base 2, gap found
if result == ("0b%s" % mask): return i
# if we got here, no gap exists
return -1
这对于大约 100k(< 1 秒)来说相当快。我很感激有关如何使更大的集合更快/更有效的提示。谢谢!