解决卡塔问题时需要优化的建议

Question

我在 codewars 上做 Katas，我有时会通过所有测试但由于超时原因而失败。您能否就如何通过重构以下代码改进我的代码提出意见。

arrA 和 arrB 是数组，rng 是一个范围，wanted 是 "odd" 或 "even"。我需要 return 一个数组，该数组包含在每个数组中存在不止一次的数字，并且在范围内并且是奇数或偶数。

def find_arr(arrA, arrB, rng, wanted)
  common = arrA && arrB

  range = (rng[0]..rng[1]).to_a.select {|num| common.include?(num)}

  range_wanted = range.select {|num| wanted == "odd" ? num.odd? : num.even?}

  numbers_twice = range_wanted.select {|num| arrA.count(num) > 1 && arrB.count(num) > 1}
end

Answer 1

这里有很多问题，主要是时间复杂度是 O(n^2) 因为最后一行计算了两个数组中出现的次数。对于 range_wanted 中的每个数字，它需要遍历两个数组的所有元素。这是非常低效的。

尝试运行使用这些参数 find_arr([], [], [1, 10_000_000], "odd") 或更大范围的 irb 中的代码。

以下是一些如何改进此代码的建议：

通过将它们存储在散列中自己计算出现次数
计数时可以跳过那些不符合要求、范围和odd/even
如果你想检查值是否在一个范围内，你应该使用 Range class 中的 cover? 方法。不要将范围更改为数组并对其进行迭代。
在这一行 range_wanted = range.select {|num| wanted == "odd" ? num.odd? : num.even?} 中，您将在每次迭代中测试 wanted == "odd"，但这永远不会改变，因为它作为参数传递。您可以将此条件移出循环

这里是重构代码。我是凭空写的，所以可能会有一些问题，但它应该能让您了解如何编写自己的解决方案。

def find_arr(arrA, arrB, rng, wanted)
  countA = Hash.new(0)
  countB = Hash.new(0)

  # If wanted == "odd" we want to test elem % 2 == 1, otherwise elem % 2 == 0
  remainder = wanted == "odd" ? 1 : 0
  range = (rng[0]..rng[1])

  arrA.each do |elem|
    if range.cover?(elem) && (elem % 2 == remainder)
      countA[elem] += 1
    end
  end

  arrB.each do |elem|
    if range.cover?(elem) && (elem % 2 == remainder)
      countB[elem] += 1
    end
  end

  result = []

  countA.each do |elem, count|
    if count > 1 && countB[elem] > 1
      result.push(elem)
    end
  end

  result
end

解决卡塔问题时需要优化的建议

Advice needed with optimization when solving Kata's

ruby

optimization

runtime