Ruby 给定一个未知数组,求其中重复片段?

pepsin · 2012年06月11日 · 最后由 chucai 回复于 2012年06月11日 · 3484 次阅读

比如[1, 2, 3, 1, 2, 3],

如何用 Ruby 实现查找重复的片段[1, 2, 3]及其位置呢?尤其是数组极大的情况下,如何更有效率的求得所有重复片段?

目前暂定的想法是利用相邻数之和先判断一次循环中所有分割出的片段是否含相同元素,然后再转化为字符串检查两片段是否相等。

各位还有更好的想法没?

何为重复片断?1算不算?1,2算不算?

#1 楼 @zhaoguobin 算啊,数组长度 2 以上的都算片段吧。

class Array
  #返回一个数组在另一个数组的所有索引
  def index_arr(arr)
    indexs = []
    (0..self.length).each do |i|
      indexs << i if self[(i...i+arr.length)] == arr
    end
    indexs
  end

  #统计一个数组在另一个数组出现的次数,允许重叠
  def count_arr(arr)
    count = 0
    (0..self.length).each do |i|
      count = count + 1 if self[(i...i+arr.length)] == arr
    end
    count
  end

  #统计一个数组在另一个数组出现的次数,重叠的不算
  def count_arr1(arr)
    count = 0
    i = 0
    len = self.length
    while i < len
      if self[(i...i+arr.length)] == arr
        count = count + 1
        i = i + arr.length
      else
        i = i + 1
      end
    end
    count
  end
end

a = [0, 6, 4, 1, 2, 3, 1, 2, 3, 1, 3, 4]

a_tmp = []
(0..a.length).each do |i|
  (0..a.length).each do |m|
    a_tmp << a[i..m] if m > i
  end
end

a_tmp = a_tmp.uniq.select{ |i| i.length>1 }

a_tmp = a_tmp.sort_by{ |i| -i.length }.select{ |i| a.count_arr(i)>1 }.collect{ |i| [i, a.index_arr(i)] }

a_tmp.each{ |i| p i }
需要 登录 后方可回复, 如果你还没有账号请 注册新账号