把列表中把所有连续 0 元素找出来

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3111 天前的主题，其中的信息可能已经有所发展或是发生改变。

比如我有列表[1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0],怎么找出连续的 0 ，并且把 0 后面的 1 的位置和 0 之前 1 的位置都标出来，有没有提出好的方法的

列表

位置

连续

出来

22 条回复 • 2016-05-06 15:27:01 +08:00

imn1

2016-05-05 10:58:39 +08:00

位运算

abutter

2016-05-05 11:05:30 +08:00

这是做题还是有具体的需求？原始的需求是啥？

administrator321

2016-05-05 11:08:27 +08:00

@abutter 具体需求，就这样格式的，大概有 10 万个这样格式的数据，有没有好方法

administrator321

2016-05-05 11:08:38 +08:00

@imn1 具体可以说说嘛

jmc891205

2016-05-05 11:20:57 +08:00

把列表右移一位，然后新列表和原列表对应的位做比较， 0-0 和 1-1 结果记为 0 ， 0-1 结果记为 1 ， 1-0 结果记为 2 则
原列表：[1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0]
新列表：[_ 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0]
比较　：[_ 1 0 2 0 0 0 0 1 0 0 2 0 0 0 0 1 0 _]
比较结果里除了首位两位， 1 的位置在新列表里就是 0 前面的 1 ， 2 的位置在原列表里就是 0 后面的 1
连续的 0 就找 1 和 2 之间元素多于 1 个的就可以了

如果是二进制数的话也是这个思想，可以利用位运算

am241

2016-05-05 11:21:15 +08:00 via Android

这种问题遍历一遍就 ok 吧？还能有更好的方法？

menc

2016-05-05 11:23:27 +08:00

@jmc891205 麻烦，一遍遍历完成的事情非要搞这么多事情

jmc891205

2016-05-05 11:23:43 +08:00

@jmc891205 又看了一遍好像二进制数的输入这样做会快一点如果输入是列表还是直接遍历一遍吧=，=

jmc891205

2016-05-05 11:24:55 +08:00

@menc 哈哈被一楼误导了因为我的工作都是跟二进制数打交道比较多所以直接拿位运算的思想来套了
楼主输入的是列表还是遍历一遍吧

loading

2016-05-05 11:26:27 +08:00

遍历一次，每一位都判断当前位和旁边的两位不就好了？

ytmsdy

2016-05-05 11:37:36 +08:00

遍历一遍， O(N)的时间复杂度，已经很快了。。。

kindjeff

2016-05-05 11:41:38 +08:00

10W 个 18 个 0 或 1 的列表？如果没有重复项的话肯定有大量连续的项。我觉得 10W 个可以先排一下序……然后连续多项只需要算出第一个项的 0 1 情况就可以推出接下去的连续项的 0 1 情况了吧（大概
随便想的并没有验算

araraloren

2016-05-05 11:50:01 +08:00

用正则表达式分分钟匹配出来，如果你说的是 10W 个长度的话
```perl6
#!/usr/bin/env perl6

for @*ARGS -> \file {
file.IO.slurp ~~ m:g/'1' '0'**2..* '1'/;
for $/.values {
say "from:" ~ .from ~ " to:" ~ .to ~ " => " ~ .Str;
}
}
```

imn1

2016-05-05 12:01:16 +08:00

漏打个问号，误导别人了
“遍历”少不了，不过用位运算应该可以跳过部分（首位置 0 后判断 bit length ）
while
length => start
首位置 0
if length<start-1 then length => end 处理（长度与位置的关系）并记录 start/end
loop

大致吧，由于 length 是跳跃的，比起 step=1 少处理一些

imn1

2016-05-05 12:07:50 +08:00

对于位数太长，不能使用位运算，就用 @araraloren 的正则思路吧
0+是指任意长度 0 的（贪婪），也可以跳跃不需要每位校验

hellosnow

2016-05-05 12:16:22 +08:00 via Android

在算游程？

administrator321

2016-05-05 12:52:56 +08:00

@loading 一个 10 万长度的这样的列表

yemenchun1

2016-05-05 13:02:00 +08:00

100 万个数, O(N*lg2(N))复杂度的, 普通计算机的完成时间是"instant", 你这个根本不用考虑算法.

realpg

2016-05-05 13:46:32 +08:00

十万个，又不是十万亿个，直接任何暴力算法对于计算机来说都不是问题

tvallday

2016-05-05 13:57:43 +08:00

Ruby solution:

num = gets.chomp

res = [] # index array for number zero

num.scan(/0/) do |c|
key = c[0].to_i
value = Regexp.last_match.offset(0)[0]
res << value
end

result = res.flat_map {|e| [e-1, e, e+1]}.select {|e| e >= 0}.uniq

result.pop if result.last == num.size

p (result - res).inspect # index array for end result

zingl

2016-05-05 14:58:27 +08:00

难道不是遍历一遍判断一下当前元素是否为 0 、前一个元素是否为 0 、确定是否记录位置就可以了，有那么复杂？

SmiteChow

2016-05-06 15:27:01 +08:00

楼主想复杂了