检查Ruby中的整数数组是否递增
我想检查一旦排序的数组值是否递增1
例如
[1, 2, 3, 4, 5] = TRUE [1, 2, 8, 9, 10] = FALSE 任何建议都非常感谢
试试这个：
def array_increments_by?(step, array) sorted = array.sort lastNum = sorted[0] sorted[1, sorted.count].each do |n| if lastNum + step != n return false end lastNum = n end true end
用法：
array_increments?(1, [0,1,2,3]) #=> true array_increments?(2, [0,2,4,6]) #=> true array_increments?(2, [0,2,4,8]) #=> false
array = [1,2,4,3] array.sort.each_cons(2).all? { |x,y| y == x + 1 }
def continguous?(arr) a = arr.sort (a.first..a.last).to_a == a end a = [2,1,3,4,5] p continguous?(a) #=> true
我跟这个：
def is_consecutive_array?(ary) sorted_array = ary.sort first_element = sorted_array.first last_element = sorted_array.last ((last_element - first_element) == ary.size - 1) && (sorted_array[0].upto(sorted_array[-1]).to_a == sorted_array) end is_consecutive_array?([1,2]) # => true is_consecutive_array?([1,2,3]) # => true is_consecutive_array?([3,2,1]) # => true is_consecutive_array?([-1,0,1]) # => true is_consecutive_array?([1,3]) # => false is_consecutive_array?([1, 2, 2, 2, 5]) # => false
这是对以前版本的更改。 我对它不满意，但无法理解为什么。 @sawa指出了上面最后一次测试中的缺陷。 如果第一个测试返回true，我添加了&&部分来进行详尽的检查。 整体效果出现在这个基准测试中：
Benchmark.bm do |_bench| ary2 = ary[0 .. -3] + ary[-1,1] _bench.report { loops.times { is_consecutive_array?(ary2) }} _bench.report { loops.times { is_consecutive_array?(ary) }} end # >> user system total real # >> 2.140000 0.200000 2.340000 ( 2.328039) # >> 18.430000 0.020000 18.450000 ( 18.442234)
大多数arrays都不是连续的，并且没有合适的组合来欺骗第一次测试。 对于那些做的人，第二次测试应该抓住它。
编辑：这里有一些基准来比较各种建议的方法。 到目前为止的答案已尽可能保留。 我不得不改变increase_by? 回答是因为它正在修补数组并且没有排序。 我不希望它意外地对其他测试或不公平的优势产生不利影响。
注意：我提出了TIMEOUT_LIMIT因为我也使测试arrays更大。
require 'benchmark' require 'timeout' TIMEOUT_LIMIT = 60 # in seconds ary = [*(1..10_000)] loops = 10_000 def is_consecutive_array?(ary) sorted_array = ary.sort first_element = sorted_array.first last_element = sorted_array.last ((last_element - first_element) == ary.size - 1) && (sorted_array[0].upto(sorted_array[-1]).to_a == sorted_array) end is_consecutive_array?([1,2]) # => true is_consecutive_array?([1,2,3]) # => true is_consecutive_array?([3,2,1]) # => true is_consecutive_array?([-1,0,1]) # => true is_consecutive_array?([1,3]) # => false is_consecutive_array?([1, 2, 2, 2, 5]) # => false def sawa(a) b = a.dup x = b.delete(b.min) nil while b.delete(x+=1) b.empty? end sawa([1,2]) # => true sawa([1,3]) # => false sawa([1,3,3]) # => false def array_increments_by?(step, array) sorted = array.sort lastNum = sorted[0] sorted[1, sorted.count].each do |n| if lastNum + step != n return false end lastNum = n end true end array_increments_by?(1,[1,2]) # => true array_increments_by?(1,[1,3]) # => false array_increments_by?(1,[1,3,3]) # => false def continguous?(arr) a = arr.sort (a.first..a.last).to_a == a end continguous?([1,2]) # => true continguous?([1,3]) # => false continguous?([1,3,3]) # => false def fgb(array) array.sort.each_cons(2).all? { |x,y| y == x + 1 } end fgb([1,2]) # => true fgb([1,3]) # => false fgb([1,3,3]) # => false # changed from a monkey-patch on Array to avoid any unintended side-effects. def increase_by?(ary, n) ary.sort # added sort to put on same ground as all other tests y = nil ary.each {|x| return false if y && ((xy) != n); y=x} true end increase_by?([1,2],1) # => true increase_by?([1,3],1) # => false increase_by?([1,3,3],1) # => false Benchmark.bm(20) do |_bench| begin testname = 'is_consecutive_array?' status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { is_consecutive_array?(ary) } } } rescue Timeout::Error => e puts "#{testname} timed out" end begin testname = 'sawa' status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { sawa(ary) } } } rescue Timeout::Error => e puts "#{testname} timed out" end begin testname = 'array_increments_by?' status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { array_increments_by?(1, ary) } } } rescue Timeout::Error => e puts "#{testname} timed out" end begin testname = 'continguous?' status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { continguous?(ary) } } } rescue Timeout::Error => e puts "#{testname} timed out" end begin testname = 'fgb' status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { fgb(ary) } } } rescue Timeout::Error => e puts "#{testname} timed out" end begin testname = 'increase_by?' status = Timeout::timeout(TIMEOUT_LIMIT) { _bench.report(testname) { loops.times { increase_by?(ary, 1) } } } rescue Timeout::Error => e puts "#{testname} timed out" end end
并且针对连续数组的结果：
# >> user system total real # >> is_consecutive_array? 18.470000 0.020000 18.490000 ( 18.476536) # >> sawa sawa timed out # >> array_increments_by? 37.070000 0.670000 37.740000 ( 37.734562) # >> continguous? 18.720000 0.890000 19.610000 ( 19.590057) # >> fgb fgb timed out # >> increase_by? 41.510000 0.610000 42.120000 ( 42.090960)
class Array def increase_by?(n) y = nil self.each {|x| return false if y && ((xy) != n); y=x} true end end [1, 2, 3, 4, 5].increase_by?(1) # => true [1, 2, 8, 9, 10].increase_by?(1) # => false
如果a[i+1]和a[i]之间的差值不等于1，那么很明显它们不是按递增顺序递增1或者根本不按升序排列（考虑到没有两个元素）数组相等）。 运行循环从零到数组长度减1。
这个不需要sort 。
a = [2, 8, 1, 9, 10] b = a.dup x = b.delete(b.min) nil while b.delete(x+=1) b.empty?
一种简短有效的方法
sort不是必需的，比较在第一个反例中断。
def increase_by? (array, step) yes = true array.reduce { |l, r| break unless yes &= ( l+step == r ); l } yes end
a = [1,2,3,4,5] a[a.size-1] == a[0] + a.size-1 TRUE
试试这个
def increase_by_one?(array) temp = array.first array.each_with_index do |val, index| return false unless temp == val-index end true end