请教一个数组取特定索引的问题

[volvo007]

感觉对算法大佬这个题目手到擒来，但是自己一下卡住了，不知道怎么用 py 优雅的实现

题目： 数组由 0，1 构成，其中连续的 1 构成了一些组，要求取出这些组的开头和结尾的索引。单独的 1 不计入。

例子： [1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1]

索引： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

返回： [[3, 5], [11, 14]]

解释： [3, 5] 和 [11, 14] 这两个区间是连续的 1，位于 [0] 和 [9] 位置的 1 由于是单个的，所以不记录

[evill]

双指针？

[jmc891205]

遍历一遍就可以了

[kuangwinnie]

```python
def getIndex(arr):
memo = [0] * len(arr)
left, right = 0, 0
while left < len(memo):
# while right < len(memo):
# if memo[right] == 1:
# right += 1
while right < len(arr) and arr[right] == 1:
right += 1
if right - left > 1:
memo[right - 1] = (right - left)
if left == right:
right += 1
left = right

res = []
for idx in range(len(arr) - 1, -1, -1):
if memo[idx] != 0:
res.append([idx -memo[idx] , idx])
res.reverse()
return res

```

[kuangwinnie]

```python
def getIndex(arr):
memo = [0] * len(arr)
left, right = 0, 0
while left < len(memo):
# while right < len(memo):
# if memo[right] == 1:
# right += 1
while right < len(arr) and arr[right] == 1:
right += 1
if right - left > 1:
memo[right - 1] = (right - left)
if left == right:
right += 1
left = right

res = []
for idx in range(len(arr) - 1, -1, -1):
if memo[idx] != 0:
res.append([idx -memo[idx] , idx])
res.reverse()
return res
```

[kuangwinnie]

```
def getIndex(arr):
memo = [0] * len(arr)
left, right = 0, 0
while left < len(memo):
# while right < len(memo):
# if memo[right] == 1:
# right += 1
while right < len(arr) and arr[right] == 1:
right += 1
if right - left > 1:
memo[right - 1] = (right - left)
if left == right:
right += 1
left = right

res = []
for idx in range(len(arr) - 1, -1, -1):
if memo[idx] != 0:
res.append([idx -memo[idx] , idx])
res.reverse()
return res
```

[kuangwinnie]

服了 到底怎么插代码啊= =

[volvo007]

@evill
@jmc891205
@kuangwinnie 谢谢楼上的各位，我再想想有没有时间复杂度更低的办法，还是说这个题目的最优时间复杂度就是 O(n) 了？

比如如果给出的不是 列表，而是 树 结构的话，要求取出所有为 1 的分支。这种题目应该往什么方向考虑可以得到最优时间解

[kuangwinnie]

@volvo007
你需要知道每个数字在这个数组中前后的信息（ like，这个数字所在的段是否长度为 1 以上）
你要优化的话我觉得可以用二分来优化，每次找可以从 n 提高到 logn
然后变成 klogn （ k 为段的数目）

变成树状结构无非就是让你更好的二分

[kuangwinnie]

到底怎么插代码啊

[volvo007]

@kuangwinnie 目前推荐的方法，是找一个网络记事本，写好了然后发链接到这里。这里有推荐，但我忘记那个名字了

[kuangwinnie]

@volvo007 懂了，codepad，我还以为回复里面可以跟主贴一样插代码

[sun1991]

提供一个简单的方法:

nums = [1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
result = [[]]
for index, num in enumerate(nums):
____if num == 1: result[-1].append(index)
____if num == 0: result.append([])

eliminate = [[min(x), max(x)] for x in result if len(x)>1]
print(eliminate)

[jmc891205]

@volvo007
logn 的时间复杂度需要你每次迭代都可以舍弃掉一半的数据不用去看
但你这个题目显然是要把所有数据至少看一遍的，所以我认为不管给的是数组还是二叉树还是什么，最优的时间复杂度就是线性了

[princelai]

```
from itertools import groupby
from operator import itemgetter

result = []
arr = [1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
for i,j in groupby(enumerate(arr), key=lambda x:x[1]==1):
if i:
j = list(j)
if len(j) > 1:
idx = list(map(itemgetter(0), j))
result.append([min(idx),max(idx)])
```

[princelai]

代码乱了贴这里，https://pastebin.ubuntu.com/p/XpzXdYyHhF/

[volvo007]

@sun1991 这个方法太好玩了，请教下大佬们都是怎么想到这种思路的 👻

[volvo007]

@princelai 谢谢指教，学到了 groupby 结合 enumerate 的用法； itemgetter 结合 map 也很有用

[owtotwo]

写了个一行实现 发现已经有老哥用了 groupby 了 所以顺便写了个效率可能高一点点的 顺便简单测了一下用时

第 15 行可能有点 tricky，可能写得不太优雅，可以尝试理解一下: )

https://pastebin.ubuntu.com/p/ybfW4wjWm9/

[princelai]

@owtotwo #18 佩服，你这个 fast 写的我都没看懂，不过我请了个外援 numpy，速度比 fast 再提高一倍以上，如果再想提高就得上 numba 了。
用你的测速函数需要提前转成 numpy 数组
```
arr2 = np.array(arr)
```
而且由于内部是 numpy.int64 类型，所以 assert 会出错，不过结果是正确的
https://pastebin.ubuntu.com/p/p6cyJjvZjR/