算法 如何获得数组里面连续的多部分

kikyous · 2013年08月14日 · 最后由 u1384048594 回复于 2014年01月27日 · 7048 次阅读
a = [1,2,3,5,6,9,10]

要得到 [1,2,3], [5,6], [9,10]

请问大家有没有比较优雅的实现

1楼 已删除

哦,搞错了,哈。

@kikyous 你分组的算法是什么? 是否可以在 chunk 里面加上你分组的算法?

[3,1,4,1,5,9,2,6,5,3,5].chunk {|n|
  n.even?
}.each {|even, ary|
  p [even, ary]
}
#=> [false, [3, 1]]
#   [true, [4]]
#   [false, [1, 5, 9]]
#   [true, [2, 6]]
#   [false, [5, 3, 5]]

这个只能 a.each 一个个遍历吧。。

现在的写法

def calc_range list
  range = []
  _last = nil
  list.each do |d|
    if !_last or (_last + 1 == d)
      range << d
    else
      range << nil
      range << d
    end
    _last = d
  end
  range.split nil
end
pry(main)> calc_range [1,2,3,5,6,9,10]
=> [[1, 2, 3], [5, 6], [9, 10]]

改进的写法

def calc_range list
  range = []
  _last = nil
  list.each do |d|
    range << nil if _last and (_last + 1 != d)
    range << d
    _last = d
  end
  range.split nil
end

#7 楼 @kikyous 能用 Array#insertnil 不?

另外为啥我这运行楼主的程序显示 undefined method `split' for [1, 2, 3, nil, 5, 6, nil, 9, 10]:Array (NoMethodError) 我好像记得 string 才有 split ...

#9 楼 @blacktulip 莫非我用的是 ruby2.0 的缘故?

#10 楼 @kikyous 我的也是啊

~  ᐅ ruby -v
ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-darwin12.4.0]

#8 楼 @blacktulip 试了一下可以用 Array#insert 插 nil 的

#11 楼 @blacktulip 我是 rails console

#11 楼 @blacktulip Array#split 确实是 rails 的扩展

#13 楼 @kikyous 怪不得,肯定是 ActiveSupport 里面的

#15 楼 @blacktulip 莫名奇妙就受了 rails 的好处,哈哈

a = [1,2,3,5,6,8,9]
indexes = []
a.each_with_index do |e, i|
  if a[i+1].to_i - e != 1
    indexes << i
  end
end
result = []
indexes.each_with_index do |e, i|
  if i == 0
    result << a[0..e]
  else
    result << a[(indexes[i - 1] + 1)..e]
  end
end
puts result.inspect

一般这种帖子都会有 @luikore 或者 @bhuztez 发个 one liner 让大家喷一下血... 等待中...

#18 楼 @blacktulip 同等待中。。。

@blacktulip ...

Array#split 是 activesupport 添加的. 如果不用 activesupport :

def calc_range list
  last = nil
  flip = false
  list.chunk do |e|
    flip ^= !(last and e == last + 1)
    last = e
    flip
  end.map &:last
end
calc_range [1,2,3,5,6,9,10,2,3,4]

#20 楼 @luikore 这次的略显不犀利。。。

#21 楼 @kikyous 抱歉, 水平有限....

#22 楼 @luikore 额,不用谦虚

#20 楼 @luikore 果然每次都能涨姿势,这次学到了 Array#chunk . thx

%w(1 2 3 4 5 6 7).in_groups_of(3) {|group| p group}
  ["1", "2", "3"]
  ["4", "5", "6"]
  ["7", nil, nil]

  %w(1 2 3).in_groups_of(2, '&nbsp;') {|group| p group}
  ["1", "2"]
  ["3", "&nbsp;"]

  %w(1 2 3).in_groups_of(2, false) {|group| p group}
  ["1", "2"]
  ["3"]

https://github.com/rails/rails/blob/ccf9577aee86ce1f766c5e8854e0c285dc38f8ac/activesupport/lib/active_support/core_ext/array/grouping.rb#L19

#25 楼 @ruby_sky 这用不上吧... 不是按个数切割

#26 楼 @blacktulip 刚开始看还以为是。。

向原数组内未相连的部分插入分隔符(比如 nil)也可以这样做:

# Suppose an array given like this
array = [1,2,3,5,6,8,9]

# Then put an delimiter
result = Range.new(array.first, array.last).map do |element|
  array.include?(element) ? element : nil
end

在之后对于 result 的处理,如果没有 ActiveSupport 的扩展,那就只好手动去 chunk 了吧。

#28 楼 @nightire 嗯,这个好,果然人多了总有好想法

#29 楼 @nightire 有一个问题,其实我的数组里面都是 Date 对象,怎么简便的生成全序的 range 呢,这个算法我在项目里面也用到了,不过还是通过循环实现的

a = [1,2,3,5,6,9,10]

arr, last = [], nil

a.each do |e|
  arr.last << e if c = (last and e == last + 1)
  arr << [e] unless c
  last = e
end

省个局部变量

a = [1,2,3,5,6,9,10]

arr = []

a.inject(nil) do |last, e|
  arr.last << e if c = (last and e == last + 1)
  arr << [e] unless c
  e
end

触目惊心,ruby 程序之泪死活要变成一行 误

a = [1,2,3,5,6,9,10]

arr = []

a.inject(nil) { |last, e| (last && e == last + 1 ? arr.last << e : arr << [e]) and e }

#32 楼 @kenshin54 嗯,这个不错

one liner

a.inject([]){|memo, n| memo.size >= 1 && n - memo[-1][-1] == 1 ? memo[-1] << n : memo << [n]; memo}

#35 楼 @quakewang 其实吧... 带分号就不算 one liner 了...

非得写一行吗? 来个正常的:

class Array
  def slice_by(n=3)
    return self if length <= n
    arr = []
    if length.even? && n==3
      each_slice(2){|i| arr << i}
    else
      arr << (self[0]..self[n-1]).to_a
      self[n..length-1].each_slice(2){|i| arr << i}
    end
    return arr
  end
end
pry(main)> [1,2,3].slice_by
=> [1, 2, 3]
pry(main)> [1,2,3,4,5].slice_by
=> [[1, 2, 3], [4, 5]]
pry(main)> [1,2,3,4,5].slice_by(4)
=> [[1, 2, 3, 4], [4, 5]]
pry(main)> [1,2,3,4,5,6].slice_by
=> [[1, 2], [3, 4], [5, 6]]
pry(main)> [1,2,3,4,5,6,7,8,9,10].slice_by
=> [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]]
pry(main)> [1,2,3,4,5,6,7,8,9,10].slice_by(5)
=> [[1, 2, 3, 4, 5], [6, 7], [8, 9], [10]]

优雅吗? 你还可以修改方法里的each_slice(2),把这个数字 2 通过传递参数改成任意你想要的。

#37 楼 @blackanger 优雅不优雅我不敢说... 但是功能完全错了...

#38 楼 @blacktulip 啊偶, 难道又看错贴了? 求科普 晕了,随便扫了一眼题。 原来是求数组里连续的元素啊啊啊啊啊啊啊啊。

#18 楼 @blacktulip

水平不够啊,只能 Python 了

reduce(lambda l,e:l and l[-1][-1]+1==e and l[:-1]+[l[-1]+[e]] or l+[[e]],[1,2,3,5,6,9,10],[])

#39 楼 @blackanger 数字不是连续的,要在不连续的地方切断

#40 楼 @bhuztez ... 不懂 python 求对应 ruby 版 不用一行也好...

#42 楼 @blacktulip

[1,2,3,5,6,9,10].inject([]){|l,e|(l!=[]&&l[-1][-1]+1==e)?l[0..-2]+[l[-1]+[e]]:l+[[e]]}
arr = [1,2,3,5,6,9,10]
f, l = arr.first, arr.last
[f - 1,*((f..l).to_a - arr),l + 1].each_cons(2).map{|s, e| arr.select{|n| n > s && n < e}}.select{|a|a.size > 0}

不太优雅, 但是比较通用,数组的元素随便定义。 楼上的写代码,只为满足楼主那一个例子吗?a = [1,2,3,5,6,9,10]

arr = [1,2,3,7,5,6,9,10,13,14,15,16,20,15,16]
result = []
b = []

arr.each_with_index do|i, index|
  b << i if (i.succ == arr[index+1]) || (i.succ != arr[index+1] && i == arr[index-1].succ)
  if i.succ != arr[index+1]
    result << b unless b.empty?
    b = []
  elsif i.succ != arr[index+1] && i == arr[index-1].succ
    b << i
    result << b
    b = []
  end
end


puts result.inspect
#=>  [[1, 2, 3], [5, 6], [9, 10], [13, 14, 15, 16], [15, 16]]

#45 楼 @blackanger

你还漏了[7] [20]吧你

[1,2,3,7,5,6,9,10,13,14,15,16,20,15,16].inject([]){|l,e|(l!=[]&&l[-1][-1]+1==e)?l[0..-2]+[l[-1]+[e]]:l+[[e]]}
=> [[1, 2, 3], [7], [5, 6], [9, 10], [13, 14, 15, 16], [20], [15, 16]]

#46 楼 @bhuztez 嗯, 7 是故意去的,只取的连续的。我说的是 jjym 的。

更短的来了...

a = [1,2,3,5,6,9,10,2,3,4]
(1..a.size).zip(a).chunk{|l,r|l-r}.map{|_,e|e.map &:last}

或者长一点但简单点的:

a.each_with_index.chunk{|l,r|l-r}.map{|_,e|e.map &:first}

#48 楼 @luikore 進撃のluikore

#50 楼 @bhuztez 我倒觉的@luikore 可读性比你那个好啊, 你那个我看着挺费劲。

#50 楼 @bhuztez 后面是有点, ea.each_with_index ...

#48 楼 @luikore

a.slice_before([0]){|e,l|e-1!=(l<<e).shift}.to_a

或者不清空状态

a.slice_before([]){|e,l|e-1!=(l<<e)[-2]}.to_a

易读版而且可以自定义什么为 “连续”

def consecutive?(x,y)
  x && y && (x-y).abs == 1
end

a.reduce([]) {|accu, num| consecutive?(accu.flatten.last, num) ? (accu.last << num; accu) : accu << [num] }

取个巧:

a = [1,2,3,5,6,8,9]
(1..9).map{|i| a.index(i) ? i : nil}.split(nil)  # [[1, 2, 3], [5, 6], [8, 9]]

#54 楼 @doitian slice_before cool! .... 不睡觉的人

#54 楼 @doitian 这个确实很酷

学到了 Array#chunk , 和 slice_before
:)

def seq(a)
  c = a.clone

  cur = [c.shift]
  ret = [cur]
  while (last = c.shift)
    if last - cur.last == 1  
      cur << last 
    else
      cur = [last]
      ret << cur
    end
  end
  ret
end

a.zip((1..a.size)).chunk{ |e,i| e-i }.map{ |x| x[1].map{ |a|a[0] } }

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册