时间戳

首页 > 解决方案 > 检测嵌套数组是否包含相似元素

ruby - 检测嵌套数组是否包含相似元素

问题描述

我有一种方法可以获取数组数组并检测是否有任何子数组出现多次，无论其顺序如何：

def has_similar_content?(array)
  array.each.with_index do |prop1, index1|
    array.each.with_index do |prop2, index2|
      next if index1 == index2

      return true if prop1.sort == prop2.sort
    end
  end

  false
end


> has_similar_content?([%w[white xl], %w[red xl]])        
=> false

> has_similar_content?([%w[blue xl], %w[xl blue cotton]])
=> false

> has_similar_content?([%w[blue xl], %w[xl blue]])
=> true

> has_similar_content?([%w[xl green], %w[red xl], %w[green xl]])        
=> true

我的问题是这种方法的运行时间，它具有二次复杂性，需要额外的数组来检测元素是否相同。

有没有更有效的方法来做到这一点？

标签： ruby

解决方案

我假设这个问题正如我对这个问题的评论中所述。

代码

def disregarding_order_any_dups?(arr)
  arr.map do |a|
    a.each_with_object(Hash.new(0)) do |k,h|
      h[k] += 1
    end
  end.uniq.size < arr.size
end

例子

disregarding_order_any_dups? [%w[white xl], %w[red xl]]
  #=> false        
disregarding_order_any_dups? [%w[blue xl],
  %w[xl blue cotton]]
  #=> false        
disregarding_order_any_dups? [%w[blue xl], %w[xl blue]]
  #=> true        
disregarding_order_any_dups? [%w[xl green], %w[red xl],
  %w[green xl]]        
  #=> true
disregarding_order_any_dups? [[1,2,3,2], [3,1,3,2],
  [2,3,1,2]]
  #=> true

复杂

如果n = arr.size和m = arr.map(&:size).max，计算复杂度为 O( n*m)。' 块中的单个语句map可以替换为a.sort，但这会将计算复杂度增加到 O( n*m*log(m))。

解释

对于最后一个示例，步骤如下。

arr = [[1,2,3,2], [3,1,3,2], [2,3,1,2]]

b = arr.map do |a|
  a.each_with_object(Hash.new(0)) do |k,h|
    h[k] += 1
  end
end
  #=> [{1=>1, 2=>2, 3=>1}, {3=>2, 1=>1, 2=>1},
  #    {2=>2, 3=>1, 1=>1}] 
c = b.uniq
  #=> [{1=>1, 2=>2, 3=>1}, {3=>2, 1=>1, 2=>1}] 
d = c.size
  #=> 2 
e = arr.size
  #=> 3 
d < e
  #=> true

表达方式

h = Hash.new(0)

创建一个计数哈希。Ruby 扩展h[k] += 1为

h[k] = h[k] + 1

哈希实例方法:[]=在左边，:[]在右边。如果h没有 key k，h[k]则将右侧替换为h的默认值，该值已定义为零，从而导致：

h[k] = 0 + 1

如果右边h有一个键k,的值不会被替换为的默认值。查看Hash::new的版本，它的参数等于哈希的默认值。h[k]kh

推荐阅读