ruby - 优化鸟类迁徙挑战

Question

我目前正在应对一项挑战，其指导方针如下：

您被要求帮助研究在整个大陆迁徙的鸟类数量。您感兴趣的每种鸟类都将由一个整数值标识。每次发现特定种类的鸟时，其 ID 号都会添加到您的目击记录中。您希望能够根据目击记录找出最常见的鸟类类型。你的任务是打印那只鸟的类型编号，如果两种或更多类型的鸟同样常见，请选择 ID 编号最小的类型。

例如，假设您的观鸟是类型arr = [1, 1, 2, 2, 3]。和各有两种1，2目击型各有一种3。选择见过两次的两种类型中较低的一种： type 1。

我编写的代码通过了大部分测试，但在超大输入时超时，我希望您能就如何优化它提出建议。

我的代码如下：

def migratoryBirds(arr)
    sorted = Hash[arr.map { |x| [x, arr.select { |y| y==x }.count] }]
    return sorted.max_by { |k,v| v }[0]
end

标签： rubyalgorithmsearch

Answer 1

您的sorted哈希可以写得更简洁一点：

sorted = arr.map { |x| [x, arr.count(x)] }.to_h

对于示例数组[1, 1, 2, 2, 3]，这相当于：

[
  [1, arr.count(1)], # counts all 1's in arr
  [1, arr.count(1)], # counts all 1's in arr (again)
  [2, arr.count(2)], # counts all 2's in arr
  [2, arr.count(2)], # counts all 2's in arr (again)
  [3, arr.count(3)]  # counts all 3's in arr
].to_h

它不仅计数1而且2两次。它还必须为每次count调用（或select在您的代码中）再次遍历整个数组。

更好的方法是遍历数组一次并使用散列来计算出现次数：

arr = [1, 1, 2, 2, 3]

sorted = Hash.new(0)
arr.each { |x| sorted[x] += 1 }

sorted #=> {1=>2, 2=>2, 3=>1}

这也可以通过以下方式写在一行中each_with_object：

sorted = arr.each_with_object(Hash.new(0)) { |x, h| h[x] += 1 }
#=> {1=>2, 2=>2, 3=>1}

Ruby 2.7 甚至有一个专门的方法tally来计算出现次数：

sorted = arr.tally
#=> {1=>2, 2=>2, 3=>1}