如何检查数组中的所有元素是否出现不超过两次？
我正在使用Ruby 2.4。 假设我有一个字符串数组（这些字符串都是字符串式的（是一个字？）整数…
["1", "2", "5", "25", "5"] 如何编写一个函数，告诉我数组中的所有元素是否在数组中出现的次数不超过两次？ 例如，这个数组
["1", "3", "3", "55", "3", "2"]
会返回false因为"3"会出现三次，但是这个数组
["20", "10", "20", "10"]
将返回true因为没有元素出现超过两次。
在我看来，这可能是一个非常简单的解决方案：
def no_more_than_twice_occur?(array) array.none? { |el| array.count(el) > 2 } end no_more_than_twice_occur?(["1", "3", "3", "55", "3", "2"]) # => false no_more_than_twice_occur?(["20", "10", "20", "10"]) # => true
可枚举的＃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"])
您可以像这样确定频率：
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的一部分。
试试这个
count = Hash.new(0) array.none? { |each| (count[each] += 1) > 2 } # => true or false
这是如何运作的？
-
Hash.new(0)创建一个默认值为0的哈希 -
none?检查所有元素的块并返回是否没有元素匹配 -
count[each] += 1增加计数（因为默认值为0所以没有nil）
这是一个最佳解决方案，因为一旦找到第一个违规元素就会中断。 此处发布的所有其他解决方案要么扫描整个arrays，要么更复杂。
注意，如果你想知道哪些元素出现两次以上（例如打印错误信息），请使用find或find_all而不是none? 。
我已经把它作为你的所有选项的基准:)
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
这是另一种方法，使用方法Array#difference ：
def twice_at_most?(arr) arr.difference(arr.uniq*2).empty? end
其中Array#difference定义如下：
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
在发现了很多用于Array#difference用途之后，我提出它被用作核心方法。 此链接中的文档说明了该方法的工作原理并提供了其使用示例。
我们来试试吧。
twice_at_most? [1, 4, 2, 4, 1, 3, 4] #=> false
这里
arr.uniq*2 #=> [1, 4, 2, 3, 1, 4, 2, 3] arr.difference(arr.uniq*2) #=> [4]
另一个例子：
twice_at_most? [1, 4, 2, 4, 1, 3, 5] #=> true
这是一款适合您的一体化方法。
def lessThanThree(arr) arr.each_with_object(Hash.new(0)) { |element,counts| counts[element] += 1 }.values.max < 3 end
基本上，取数组，迭代创建散列并计算每次出现，然后values方法只生成一个包含所有计数（值）的数组，然后max找到最高值。 我们检查是否小于3，如果是，则返回true，否则返回false。 您可以使用代码块替换true或false。
为了避免大量的临时开销，只需sort数组进行sort ，然后将其拆分为类似元素的块。 然后，您可以找到最长的块：
def max_count(arr) arr.sort.slice_when { |a,b| a != b }.map(&:length).max.to_i end max_count(%w[ 1 3 3 55 3 2 ]) # => 3 max_count(%w[ 1 3 55 3 2 ]) # => 2 max_count([ ]) # => 0
只是为了好玩这里使用each_cons和使用none?的一种方式none? 正如Wayne Conrad在他的回答中所使用的那样。
arr.sort_by(&:to_i).each_cons(3).none? { |a,b,c| a == b && b == c }
对于数组中的每个唯一项，计算该元素在数组中出现的次数。 在这些值中，检查max是否<= 2。
def max_occurence_at_most_2?(array) array.uniq.map{ |element| array.count(element) }.max <= 2 end
未针对速度进行优化。