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
kunimi
V2EX  ›  Python

卡住了,问大家一个Python的算法问题吧

  •  
  •   kunimi · 2013-06-28 18:04:36 +08:00 · 4758 次点击
    这是一个创建于 4169 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有如下这样一个list - A:
    [0, 0, 0, 2295, 2295, 1530, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 1785, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 0, 0, 0, 0, 0, 1275, 1530, 1530, 1530, 1530, 1530, 0, 0, 0, 0, 0, 0]

    在数目不等的0中间排列着数目不等的正整数,现在需要得到:
    1. 被0隔开的连续正整数的数目(不是总数,而是要得到每一组中正整数的数目,比如上面的例子中,第一组的数量为3,第二组为8)
    2. 每组正整数在list中index范围,比如第一组是A[3]到A[5]

    想了一个下午,虽然实现起来不难,但是都挺麻烦的,大家有没有什么好的思路?
    23 条回复    1970-01-01 08:00:00 +08:00
    chairuosen
        1
    chairuosen  
       2013-06-28 18:11:57 +08:00
    不懂phthon,只有思路行不行
    chisj
        2
    chisj  
       2013-06-28 18:15:02 +08:00
    没有思路就穷举。
    所以我第一眼看到就想for循环。。
    best1a
        3
    best1a  
       2013-06-28 18:15:47 +08:00
    (2)不是隐含(1)了么,直接遍历一遍O(n)不行么?
    chairuosen
        4
    chairuosen  
       2013-06-28 18:18:51 +08:00
    拙见:一个一个加,和与之前的和对比,有变多和不变两个状态,
    每一次不变到变多,开始记录变多个数。每一次变多到不变,输出之前变多这个状态的个数
    第二问不懂
    Saito
        5
    Saito  
       2013-06-28 18:40:46 +08:00
    r = []
    m = [0, 0, 0, 2295, 2295, 1530, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 1785, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 0, 0, 0, 0, 0, 1275, 1530, 1530, 1530, 1530, 1530, 0, 0, 0, 0, 0, 0]
    lastest = current = 0
    m.each_with_index do |n, i|
    lastest = current
    current = n
    if current != 0
    if lastest == 0
    r << i
    end
    else
    if lastest != 0
    r << i - 1
    end
    end
    end

    puts r
    puts r.each_slice(2) {|a| p a}
    puts r.each_slice(2).map{|a| a[1] - a[0] + 1 }

    结果:
    3
    5
    11
    18
    24
    30
    36
    41
    [3, 5]
    [11, 18]
    [24, 30]
    [36, 41]
    nil
    3
    8
    7
    6
    [Finished in 0.0s]
    Saito
        6
    Saito  
       2013-06-28 18:42:43 +08:00
    Ruby版
    ruoyu0088
        7
    ruoyu0088  
       2013-06-28 19:08:55 +08:00
    第一个问题可以用如下的一条语句:

    [len(list(g)) for v, g in itertools.groupby((bool(x) for x in a)) if v]

    第二个问题稍微复杂一点,分第0个元素是否为0,有两种情况:

    counts = (len(list(g)) for v, g in itertools.groupby((bool(x) for x in a)))
    acc = itertools.accumulate(counts)
    acc = itertools.chain([0], acc) if a[0] else acc
    list(zip(acc, acc))

    这里得到的index范围与Python的切片定义相同,包括start,不包括end。

    itertools.accumulate是python 3.2新增加的。
    Perry
        8
    Perry  
       2013-06-28 22:03:00 +08:00
    最近在学习Ruby,所以。。

    http://gist.github.com/5884899
    switch
        9
    switch  
       2013-06-28 22:39:29 +08:00
    这是 Javascript 版的实现:

    var num_arr = []; // 保存连续正整数的数目数组
    var idx_arr = []; // 保存每个连接正整数开始位置的索引,如果需要获取第 i 组正整数的结束位置的索引,可以通过 idx_arr[i] + num_arr[i] - 1 来获取
    for (var i = 0, num_arr = [], idx_arr = [], len = list.length; i < len; i++) {
    if (0 == list[i]) continue;
    idx_arr.push(i);
    for (var j = i + 1; j < len && list[j]; j++);
    num_arr.push(j - i);
    i = j;
    }
    cassyfar
        10
    cassyfar  
       2013-06-28 23:07:53 +08:00
    我感觉怎么都要至少遍历一次 时间复杂度 O(n)
    坐等能人给出nb算法
    wang2191195
        11
    wang2191195  
       2013-06-29 00:08:10 +08:00
    flag = False
    res = []
    start = -1
    end = -1
    for i in xrange(len(l)):
    if l[i] == 0:
    if i != 0 and flag == True:
    end = i - 1
    flag = False
    res.append((start,end))
    continue
    if not flag:
    start = i
    flag = True
    这样应该还好吧?不太麻烦=。=
    kylefeng
        12
    kylefeng  
       2013-06-29 00:33:05 +08:00
    最近在看Clojrue所以...
    <script src="https://gist.github.com/kylefeng/5886031.js"></script>
    skydiver
        13
    skydiver  
       2013-06-29 00:37:35 +08:00
    skydiver
        14
    skydiver  
       2013-06-29 00:38:20 +08:00
    @kylefeng 好像插不进来?再试试

    http://gist.github.com/kylefeng/5886031
    kylefeng
        15
    kylefeng  
       2013-06-29 00:45:15 +08:00
    额,还不太会贴gist,再试试
    http://gist.github.com/5886031
    VYSE
        16
    VYSE  
       2013-06-29 00:47:53 +08:00
    bucket = []
    [bucket[-1].append(idx) if val > 0 else bucket.append([]) for idx, val in enumerate(A)]
    [i for i in bucket if i]

    底下就好用了呗
    jander
        17
    jander  
       2013-06-29 07:32:45 +08:00
    ```
    A = [0, 0, 0, 2295, 2295, 1530, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 1785, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 0, 0, 0, 0, 0, 1275, 1530, 1530, 1530, 1530, 1530, 0, 0, 0, 0, 0, 0]

    B = []

    def foo(i, data):
    if data:
    if i==0 or A[i-1]:
    B[-1].append([data, i])
    else:
    B.append([[data, i]])

    for i, data in enumerate(A):
    foo(i, data)

    for m in B:
    print m
    ```
    Golevka
        18
    Golevka  
       2013-06-29 12:59:04 +08:00   ❤️ 1
    @cassyfar 理论下界就是O(n), 不存在时间复杂度更小的算法
    supersheep
        19
    supersheep  
       2013-06-29 13:52:22 +08:00
    就遍历一遍咯,又不麻烦,让人能够一下看明白代码是干嘛的才比较重要。
    IwfWcf
        20
    IwfWcf  
       2013-06-29 23:00:27 +08:00
    不就是扫一遍就能知道的东西吗,和算法有什么关系了……
    xidianlz
        21
    xidianlz  
       2013-06-30 00:48:33 +08:00
    试试couting sort的思想把
    ivanlw
        22
    ivanlw  
       2013-06-30 02:28:52 +08:00 via iPhone
    @ruoyu0088 请问那个一句话的是什么语法呢
    ruoyu0088
        23
    ruoyu0088  
       2013-06-30 09:10:17 +08:00
    @ivanlw, 用到了itertools模块,generator expression, list comprehension
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1063 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 22:15 · PVG 06:15 · LAX 14:15 · JFK 17:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.