V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
volvo007
V2EX  ›  Python

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

  •  
  •   volvo007 · 2020-10-22 12:45:59 +08:00 · 1847 次点击
    这是一个创建于 1253 天前的主题,其中的信息可能已经有所发展或是发生改变。

    感觉对算法大佬这个题目手到擒来,但是自己一下卡住了,不知道怎么用 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 由于是单个的,所以不记录

    19 条回复    2020-10-23 01:07:28 +08:00
    evill
        1
    evill  
       2020-10-22 13:19:00 +08:00
    双指针?
    jmc891205
        2
    jmc891205  
       2020-10-22 13:38:17 +08:00   ❤️ 1
    遍历一遍就可以了
    kuangwinnie
        3
    kuangwinnie  
       2020-10-22 13:43:41 +08:00   ❤️ 1
    ```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
        4
    kuangwinnie  
       2020-10-22 13:45:07 +08:00
    ```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
        5
    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
        6
    kuangwinnie  
       2020-10-22 13:47:47 +08:00
    服了 到底怎么插代码啊= =
    volvo007
        7
    volvo007  
    OP
       2020-10-22 13:50:02 +08:00
    @evill
    @jmc891205
    @kuangwinnie 谢谢楼上的各位,我再想想有没有时间复杂度更低的办法,还是说这个题目的最优时间复杂度就是 O(n) 了?

    比如如果给出的不是 列表,而是 树 结构的话,要求取出所有为 1 的分支。这种题目应该往什么方向考虑可以得到最优时间解
    kuangwinnie
        8
    kuangwinnie  
       2020-10-22 13:52:09 +08:00
    @volvo007
    你需要知道每个数字在这个数组中前后的信息( like,这个数字所在的段是否长度为 1 以上)
    你要优化的话我觉得可以用二分来优化,每次找可以从 n 提高到 logn
    然后变成 klogn ( k 为段的数目)

    变成树状结构无非就是让你更好的二分
    kuangwinnie
        9
    kuangwinnie  
       2020-10-22 13:52:19 +08:00
    到底怎么插代码啊
    volvo007
        10
    volvo007  
    OP
       2020-10-22 13:52:31 +08:00
    @kuangwinnie 目前推荐的方法,是找一个网络记事本,写好了然后发链接到这里。这里有推荐,但我忘记那个名字了
    kuangwinnie
        11
    kuangwinnie  
       2020-10-22 13:53:04 +08:00
    @volvo007 懂了,codepad,我还以为回复里面可以跟主贴一样插代码
    sun1991
        12
    sun1991  
       2020-10-22 14:06:30 +08:00   ❤️ 1
    提供一个简单的方法:

    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
        13
    jmc891205  
       2020-10-22 14:07:12 +08:00
    @volvo007
    logn 的时间复杂度需要你每次迭代都可以舍弃掉一半的数据不用去看
    但你这个题目显然是要把所有数据至少看一遍的,所以我认为不管给的是数组还是二叉树还是什么,最优的时间复杂度就是线性了
    princelai
        14
    princelai  
       2020-10-22 14:15:30 +08:00   ❤️ 1
    ```
    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
        15
    princelai  
       2020-10-22 14:17:07 +08:00
    volvo007
        16
    volvo007  
    OP
       2020-10-22 14:21:03 +08:00
    @sun1991 这个方法太好玩了,请教下大佬们都是怎么想到这种思路的 👻
    volvo007
        17
    volvo007  
    OP
       2020-10-22 14:29:36 +08:00
    @princelai 谢谢指教,学到了 groupby 结合 enumerate 的用法; itemgetter 结合 map 也很有用
    owtotwo
        18
    owtotwo  
       2020-10-22 18:13:59 +08:00   ❤️ 1
    写了个一行实现 发现已经有老哥用了 groupby 了 所以顺便写了个效率可能高一点点的 顺便简单测了一下用时

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

    https://pastebin.ubuntu.com/p/ybfW4wjWm9/
    princelai
        19
    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/
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   983 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 20:30 · PVG 04:30 · LAX 13:30 · JFK 16:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.