在整数列表中找到最长的连续0序列。

Question

A = [1,2,0,0,3,4,5,-1,0,2,-1,-3,0,0,0,0,0,0,0,0,-2,-3,-4,-5,0,0,0]

返回列表中最长的连续的0的起始和结束索引。 由于上述列表中最长的连续的0是 0,0,0,0,0,0,0,0，因此应该返回12,19作为起始和结束索引。请帮忙提供一行Python代码。

我尝试过：

k = max(len(list(y)) for (c,y) in itertools.groupby(A) if c==0)
print(k)

现在，如何找到最长序列的起始和结束索引呢？

返回的最大长度为8。

- Nikita Gupta

---

所以，您已经有了一种方法，大概是一些代码，可能还有运行该代码的结果。 您的问题是什么？ - TigerhawkT3

我需要用一行Python代码来编写这个。 - Nikita Gupta

那不是一个问题，那是一个任务。 - TigerhawkT3

看起来你想让我们为你编写一些代码。虽然很多用户愿意为有困难的程序员编写代码，但他们通常只会在发帖者已经尝试过自己解决问题时才提供帮助。展示这种努力的好方法是包括你已经编写的代码、示例输入（如果有的话）、期望输出以及你实际得到的输出（输出、跟踪等）。提供的细节越多，你可能会收到更多的答案。请查看FAQ和提问的智慧。 - TigerhawkT3

请检查我的代码。 - Nikita Gupta

Answer 1

你可以先使用enumerate将项目与索引打包，然后使用itertools.groupby(list,operator.itemgetter(1))按项目分组，使用list(y) for (x,y) in list if x == 0仅过滤出0，最后使用max(list, key=len)获取最长的序列。

import itertools,operator
r = max((list(y) for (x,y) in itertools.groupby((enumerate(A)),operator.itemgetter(1)) if x == 0), key=len)
print(r[0][0]) # prints 12
print(r[-1][0]) # prints 19

- ymonad

Answer 2

你可以尝试这个方法：

 A = [1,2,0,0,3,4,5,-1,0,2,-1,-3,0,0,0,0,0,0,0,0,2,-3,-4,-5,0,0,0]

count = 0
prev = 0
indexend = 0
for i in range(0,len(A)):
    if A[i] == 0:
        count += 1
    else:            
      if count > prev:
        prev = count
        indexend = i
      count = 0

print("The longest sequence of 0's is "+str(prev))
print("index start at: "+ str(indexend-prev))
print("index ends at: "+ str(indexend-1))

输出：

The longest sequence of 0's ist 8

index start at: 12

index ends at: 19

- Seek Addo

---

如果最长序列包括列表中的最后一项，则您的解决方案将失败。当然，这可以通过在for循环之后直接添加最终的(if count > prev ....)来轻松解决。 - a20

Answer 3

一个很好的简洁的本地Python方法。

target = 0
A = [1,2,0,0,3,4,5,-1,0,2,-1,-3,0,0,0,0,0,0,0,0,2,-3,-4,-5,0,0,0]

def longest_seq(A, target):
    """ input list of elements, and target element, return longest sequence of target """
    cnt, max_val = 0, 0 # running count, and max count
    for e in A: 
        cnt = cnt + 1 if e == target else 0  # add to or reset running count
        max_val = max(cnt, max_val) # update max count
    return max_val

- Matt Cliff

Answer 4

现在你已经知道了长度，找到原始列表中的那个长度为k的0序列。将这些内容扩展成一行代码，最终你会得到以下结果：

# k is given in your post
k_zeros = [0]*k
for i in range(len(A)-k):
    if A[i:i+k] == k_zeros:
        break
# i is the start index; i+k-1 is the end

现在你能把这个封装到一个语句里面吗？

- Prune

Answer 5

好的，作为一行很恶心的代码！

"-".join([sorted([list(y) for c,y in itertools.groupby([str(v)+"_"+str(i) for i,v in enumerate(A)], lambda x: x.split("_")[0]) if c[0] == '0'],key=len)[-1][a].split("_")[1] for a in [0,-1]])

它通过将[1,2,0...]转换为["1_0","2_1","0_2",..]来跟踪索引，然后进行一些拆分和解析。

是的，这很丑陋，你应该选择其他答案，但我想分享一下。

- mitoRibo

Answer 6

A = [1,2,0,0,3,4,5,-1,0,2,-1,-3,0,0,0,2,-3,-4,-5,0,0,0,0]

count = 0
prev = 0
indexend = 0
indexcount = 0
for i in range(0,len(A)):
    if A[i] == 0:
       count += 1
       indexcount = i
    else:            
       if count > prev:
       prev = count
       indexend = i
       count = 0

if count > prev:
   prev = count
   indexend = indexcount

print("The longest sequence of 0's is "+str(prev))
print("index start at: "+ str(indexend-prev))
print("index ends at: "+ str(indexend-1))

同时需要考虑最长的0序列是否在末尾。

输出

 The longest sequence of 0's is 4
 index start at: 18
 index ends at: 21

- hishatrughan

Answer 7

如果您想完全避免使用Python迭代，可以使用Numpy。例如，对于非常长的序列，使用for循环可能相对较慢。此方法将在底层使用预编译的C for循环。缺点是这里有多个for循环。尽管如此，总体而言，下面的算法应该在更长的序列上获得速度提升。

import numpy as np
def longest_sequence(bool_array):
    where_not_true = np.where(~bool_array)[0]
    lengths_plus_1 = np.diff(np.hstack((-1,where_not_true,len(bool_array))))
    index          = np.cumsum(np.hstack((0,lengths_plus_1)))
    start_in_lngth = np.argmax(lengths_plus_1)
    start          = index[         start_in_lngth]
    length         = lengths_plus_1[start_in_lngth] - 1
    return start, length

t = np.array((0,1,0,1,1,1,0,0,1,1,0,1))
print(longest_sequence(t==0))
print(longest_sequence(t==1))
p = np.array((0,0,0,1,0,1,1,1,0,0,0,1,1,0,1,1,1,1))
print(longest_sequence(p==0))
print(longest_sequence(p==1))

- GaryK

Answer 8

This solution i submitted in Codility with 100 percent efficieny.
    class Solution {
        public int solution(int N) {
            int i = 0;
                int gap = 0;
                `bool startZeroCount = false;
                List<int> binaryArray = new List<int>();
                while (N > 0)
                {
                    binaryArray.Add(N % 2);
                    N = N / 2;
                    i++;
                }
                
                List<int> gapArr = new List<int>();
                for (int j = i-1; j >= 0; j--)
                {
                    if (binaryArray[j] == 1)
                    {
                        if(startZeroCount)
                        {
                            gapArr.Add(gap);
                            gap = 0;
                           
                        }
                        startZeroCount = true;
                    }
                    else if(binaryArray[j] == 0)
                    {
                        if (startZeroCount)
                            gap++;
                    }                
                }
                gapArr.Sort();            
                if (gapArr.Count != 0)
                    return gapArr[gapArr.Count - 1];
                else return 0;enter code here
        }
    }

- vivekinall