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

```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

2020-10-22 13:45:07 +08:00

kuangwinnie

2020-10-22 13:47:15 +08:00

```
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

2020-10-22 13:47:47 +08:00

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

volvo007

2020-10-22 13:50:02 +08:00

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

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

kuangwinnie

2020-10-22 13:52:09 +08:00

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

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

kuangwinnie

2020-10-22 13:52:19 +08:00

到底怎么插代码啊

volvo007

2020-10-22 13:52:31 +08:00

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

kuangwinnie

2020-10-22 13:53:04 +08:00

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

sun1991

2020-10-22 14:06:30 +08:00

提供一个简单的方法:

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

2020-10-22 14:07:12 +08:00

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

princelai

2020-10-22 14:15:30 +08:00

```
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

2020-10-22 14:17:07 +08:00

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

volvo007

2020-10-22 14:21:03 +08:00

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

volvo007

2020-10-22 14:29:36 +08:00

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

owtotwo

2020-10-22 18:13:59 +08:00

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

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

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

princelai

2020-10-23 01:07:28 +08:00

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