如何检查数组中的所有元素是否出现不超过两次？

Question

我正在使用Ruby 2.4.假设我有一个字符串数组(这些字符串都是字符串式的(这是一个字？)整数...

["1", "2", "5", "25", "5"]

如何编写一个函数来告诉我数组中的所有元素是否在数组中出现的次数不超过两次？例如,这个数组

["1", "3", "3", "55", "3", "2"]

将返回false因为"3"发生三次,但这个数组

["20", "10", "20", "10"]

会返回,true因为没有一个元素出现超过两次.

Answer 1

您可以像这样确定频率:

frequency = array.reduce(Hash.new(0)) do |counts, value|
  counts[value] += 1
  counts
end
# => { "1" => 1, "3" => 3, "55" => 1, "2" => 1 }

你可以检查它们中的任何一个是否发生超过两次这样:

frequency.values.max > 2

如果你想很好地包装它,可以将它添加到Enumerable:

module Enumerable
  def frequency
    f = Hash.new(0)
    each { |v| f[v] += 1 }
    f
  end
end

然后你的情况很简单:

array.frequency.values.max > 2

注意:这是Facets的一部分.

Answer 2

可枚举#group_by将为此做重任:

def no_element_present_more_than_twice?(a)   
  a.group_by(&:itself).none? do |_key, values|
    values.count > 2
  end
end

p no_element_present_more_than_twice?(["1", "3", "3", "55", "3", "2"])
# => false
p no_element_present_more_than_twice?(["20", "10", "20", "10"])

Answer 3

我已经把它作为你的所有选项基准测试:)

Running each test 1024 times. Test will take about 34 seconds.
_akuhn is faster than _vlasiak by 16x ± 1.0
_vlasiak is faster than _wayne by 3.5x ± 0.1
_wayne is faster than _cary by 10.0% ± 1.0%
_cary is faster than _oneneptune by 10.09% ± 1.0%
_oneneptune is similar to _coreyward
_coreyward is faster than _tadman by 10.0% ± 1.0%
_tadman is faster than _sagarpandya82 by 10.0% ± 1.0%
_sagarpandya82 is faster than _glykyo by 80.0% ± 1.0%

正如您所看到的,@ akuhn的答案比其他算法的表现要好得多,因为一旦找到匹配,它就会提前退出.

注意:我编辑了答案以产生相同的结果,但没有编辑任何结果以进行优化.

这是生成基准的脚本:

require 'fruity'

arr = Array.new(1000) { |seed|
  # seed is used to create the same array on each script run,
  # hence the same benchmark results will be produced
  Random.new(seed).rand(1..10).to_s
}

class Array
  def difference(other)
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
    reject { |e| h[e] > 0 && h[e] -= 1 }
  end
end

compare do
  _coreyward do
    arr.reduce(Hash.new(0)) { |counts, value|
      counts[value] += 1
      counts
    }.max[1] <= 2
  end

  _wayne do
    arr.group_by(&:itself).none? do |_key, values|
      values.count > 2
    end
  end

  _sagarpandya82 do
    arr.sort_by(&:to_i).each_cons(3).none? { |a,b,c| a == b && b == c }
  end

  _tadman do
    arr.sort.slice_when { |a,b| a != b }.map(&:length).max.to_i <= 2
  end

  _cary do
    arr.difference(arr.uniq*2).empty?
  end

  _akuhn do
    count = Hash.new(0)
    arr.none? { |each| (count[each] += 1) > 2 }
  end

  _oneneptune do
    arr.each_with_object(Hash.new(0)) { |element,counts|
      counts[element] += 1
    }.values.max < 3
  end

  _glykyo do
    arr.uniq.map{ |element| arr.count(element) }.max <= 2
  end

  _vlasiak do
    arr.none? { |el| arr.count(el) > 2 }
  end

end

Answer 4

试试这个

count = Hash.new(0)
array.none? { |each| (count[each] += 1) > 2 }
# => true or false

这是如何运作的？

• Hash.new(0) 使用默认值创建哈希 0
• none? 检查所有元素的块并返回是否没有元素匹配
• count[each] += 1增加计数(nil自默认值以来没有任何情况0)

这是一种最佳解决方案,因为一旦找到第一个违规元素就会中断.此处发布的所有其他解决方案要么扫描整个阵列,要么更复杂.

注意,如果你想知道哪些元素出现两次以上(例如打印错误信息),请使用find或find_all代替none?.