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

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

2013-06-28 18:11:57 +08:00

不懂phthon，只有思路行不行

chisj

2013-06-28 18:15:02 +08:00

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

best1a

2013-06-28 18:15:47 +08:00

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

chairuosen

2013-06-28 18:18:51 +08:00

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

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

2013-06-28 18:42:43 +08:00

Ruby版

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

2013-06-28 22:03:00 +08:00

最近在学习Ruby，所以。。

http://gist.github.com/5884899

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

2013-06-28 23:07:53 +08:00

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

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

2013-06-29 00:33:05 +08:00

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

skydiver

2013-06-29 00:37:35 +08:00

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

skydiver

2013-06-29 00:38:20 +08:00

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

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

kylefeng

2013-06-29 00:45:15 +08:00

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

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

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