函数可查找列表中最长运行的开始和结束的索引

Question

我正试图编写代码，在布尔值列表中找到最长的运行，并返回该运行的第一个和最后一个值的索引。例如，如果L为[False，False，True，False，False，False，False，True，True，False，False]。则函数将返回(3，6(，因为False的最长游程是从3到6。这就是我目前所拥有的，但它不能正常工作。

def longestFalse(L):
endindex = 0
maxcount=0
counter=0
for i in range(len(L)):
if L[i] == False:
counter += 1
elif L[i] == True:
if counter>maxcount:
maxcount = counter
endindex = i
counter = 0
elif i == len(L) - 1 :
if L[i-1] == L[i]:
counter += 1
maxcount = count
endindex = i
return endindex-maxcount,endindex-1

Answer 1

您可以跟踪起始索引和迄今为止最长运行的长度，以及当前运行的起始索引，如果当前索引减去当前运行的开始索引大于迄今为止最长运行的长度，则将当前起始索引和所述长度设为新的起始索引和最长运行长度：

def longest_false(L):
start = max_start = None
max_size = -1
for i, v in enumerate(L):
if v:
start = None
else:
if start is None:
start = i
if i - start > max_size:
max_start = start
max_size = i - start
if max_start is None:
return None, None # in case there is no False at all in the given list
return max_start, max_start + max_size

Answer 2

使用itertools.groupby:

from itertools import groupby
values = [False, False, True, False, False, False, False, True, True, False, False]
start = 0
runs = []
for key, run in groupby(values):
length = sum(1 for _ in run)
runs.append((start, start + length - 1))
start += length
result = max(runs, key=lambda x: x[1] - x[0])
print(result)

输出

(3, 6)

Answer 3

具有itertools.groupby功能的更快迭代版本：

from itertools import groupby
def get_longest_run(lst):
curr_len, run_span = 0, 0
for k, gr in groupby(lst):
len_ = len(list(gr))
if (run_span and len_ > (run_span[1] + 1) - run_span[0]) or len_ > curr_len:
run_span = (curr_len, curr_len + len_ - 1)
curr_len += len_
return run_span
lst = [False, False, True, False, False, False, False, True, True, False, False]
print(get_longest_run(lst))   # (3, 6)

---

时间性能比较(与之前的答案(：

In [144]: lst = [False, False, True, False, False, False, False, True, True, False, False]                                   
In [145]: def get_longest_run_deniel(lst): 
...:     start = 0 
...:     runs = [] 
...:     for key, run in groupby(lst): 
...:         length = sum(1 for _ in run) 
...:         runs.append((start, start + length - 1)) 
...:         start += length 
...:  
...:     result = max(runs, key=lambda x: x[1] - x[0]) 
...:     return result 
...:                                                                                                                    
In [146]: def get_longest_run(lst): 
...:     curr_len, run_span = 0, 0 
...:     for k, gr in groupby(lst): 
...:         len_ = len(list(gr)) 
...:         if (run_span and len_ > (run_span[1] + 1) - run_span[0]) or len_ > curr_len: 
...:             run_span = (curr_len, curr_len + len_ - 1) 
...:         curr_len += len_ 
...:  
...:     return run_span 
...:                                                                                                                    
In [147]: %timeit get_longest_run_deniel(lst)                                                                                
6.06 µs ± 168 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [148]: %timeit get_longest_run(lst)                                                                                       
3.67 µs ± 131 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Answer 4

作为CS的一年级学生，我在这里有一个解决方案，你可以很容易地理解

def longestFalse(L):
count = -1 #Set count and highest count to -1 so that it will count at correct index
highest_count = -1
index_of_highest_count = []
L.insert(len(L),True) #This to account for False being at the end of the list
for i in range(len(L)):
if L[i] == False:
count += 1
else: #When encounter True
if count > highest_count: 
highest_count = count
index_of_highest_count.pop() if index_of_highest_count else False 
#If statement after pop to ensure no error when list is empty
index_of_highest_count.append(i-1) #Decrease index by 1 due to it currently at True
count = -1 #Reset count when encounter True
count = -1 #Reset count when there is only one run of False.
L.pop() #Remove the last index placeholder 'True' when loop is done.
if len(index_of_highest_count) == 0:
return (None,None)
return(index_of_highest_count[0]-highest_count,index_of_highest_count[0])