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

[kunimi]

有如下这样一个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]

想了一个下午，虽然实现起来不难，但是都挺麻烦的，大家有没有什么好的思路？

[chairuosen]

不懂phthon，只有思路行不行

[chisj]

没有思路就穷举。
所以我第一眼看到就想for循环。。

[best1a]

（2）不是隐含（1）了么，直接遍历一遍O（n）不行么？

[chairuosen]

拙见：一个一个加，和与之前的和对比，有变多和不变两个状态，
每一次不变到变多，开始记录变多个数。每一次变多到不变，输出之前变多这个状态的个数
第二问不懂

[Saito]

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]

Ruby版

[ruoyu0088]

第一个问题可以用如下的一条语句：

[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]

最近在学习Ruby，所以。。

http://gist.github.com/5884899

[switch]

这是 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]

我感觉怎么都要至少遍历一次 时间复杂度 O(n)
坐等能人给出nb算法

[wang2191195]

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]

最近在看Clojrue所以...
<script src="https://gist.github.com/kylefeng/5886031.js"></script>

[skydiver]

@kylefeng http://gist.github.com/kylefeng/5886031.js

[skydiver]

@kylefeng 好像插不进来？再试试

http://gist.github.com/kylefeng/5886031

[kylefeng]

额，还不太会贴gist，再试试
http://gist.github.com/5886031

[VYSE]

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]

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

@cassyfar 理论下界就是O(n), 不存在时间复杂度更小的算法

[supersheep]

就遍历一遍咯，又不麻烦，让人能够一下看明白代码是干嘛的才比较重要。

[IwfWcf]

不就是扫一遍就能知道的东西吗，和算法有什么关系了……

[xidianlz]

试试couting sort的思想把

[ivanlw]

@ruoyu0088 请问那个一句话的是什么语法呢

[ruoyu0088]

@ivanlw, 用到了itertools模块，generator expression, list comprehension