检测嵌套数组是否包含类似元素

Question

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

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

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

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

Answer 1

这种方式更简单：

array.
  group_by(&:sort).
  transform_values(&:length).
  values.any? { |count| count > 1 }

Answer 2

我假设问题是在我对这个问题的评论中所说的。

码

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没有密钥k，则右边的h[k]将替换为h的默认值，该默认值已定义为等于零，从而导致：

h[k] = 0 + 1   

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

Answer 3

这仍然是二次的，但速度更快：

def has_similar_content?(array)
  # sort subarray only once. O( n * m * log(m) )
  sorted_array= array.map(&:sort)

  # if you can change the input array, this prevent object allocation :
  # array.map!(&:sort!)

  # compare each pair only once O( n * n/2 )
  nb_elements= sorted_array.size
  0.upto(nb_elements - 1).each do |i|
    (i + 1).upto(nb_elements - 1).each do |j|
      return true if sorted_array[i] == sorted_array[j]
    end
  end
  return false
end