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

• 資深大佬 : 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/