如何返回数组中的第三个最大数字

我回答编程问题的代码逻辑是:

找到输入数组中的最大数字.

将该号码存储在新阵列中.

从输入数组中删除该数字.

重复#1-3,直到我在新数组中有三个元素.

选择要返回的数组的最后一个元素.

我的代码返回三个10,而不是数组中的三个最大元素,10,8和4.我认为这可能是因为一旦内部while循环完成,代码就无法返回到它？

我的测试代码是:

puts(third_greatest([8, 1, 10, 4])).to_s

我的代码是:

def third_greatest(nums)
  greatest_number = nil
  three_greatest = []

  three_greatest_idx = 0

  while three_greatest_idx < 3
    number_idx = 0

    while number_idx < nums.length
      current_number = nums[number_idx]

      if greatest_number == nil
        greatest_number = current_number
      elsif greatest_number < current_number
        greatest_number = current_number
      end

      number_idx += 1
    end

    three_greatest.unshift(greatest_number)
    nums.delete(greatest_number)
    three_greatest_idx += 1
  end

  return three_greatest
end

tadman.. 12

一旦你开始考虑解决像这样的问题,Ruby方式,我的意思是更多地依赖于Enumerable并表达你的意图作为一系列简单的操作,经常链接在一起,然后解决方案变得更容易找到.

例如,要找到任意数组中的三个最高数字,显而易见的解决方案可能是:

def three_greatest(list)
  list.sort.reverse.first(3)
end

对列表进行排序,默认情况下从最低到最高,然后将其反转,使其从最高到最低.最后一个操作是复制前三个entires.这看起来非常合理,因为它非常清楚地表达了您的意图并且运作良好.

问题是如果你仔细观察Enumerable产品,可以使用更简单的解决方案max:

def three_greatest(list)
  list.max(3)
end

这里要学到的教训是,Enumerable库与机械工具箱不同,它拥有大量有用的工具.重要的是要花一些时间来至少阅读那里的内容,这样你就不会浪费时间重新发明已经存在于优雅形式的东西.

换句话说,在解决问题时,请检查问题是否已经解决.在许多情况下,你会发现有一种工具可以完全满足您的需求.

1> tadman..：

---

一旦你开始考虑解决像这样的问题,Ruby方式,我的意思是更多地依赖于Enumerable并表达你的意图作为一系列简单的操作,经常链接在一起,然后解决方案变得更容易找到.

例如,要找到任意数组中的三个最高数字,显而易见的解决方案可能是:

def three_greatest(list)
  list.sort.reverse.first(3)
end

对列表进行排序,默认情况下从最低到最高,然后将其反转,使其从最高到最低.最后一个操作是复制前三个entires.这看起来非常合理,因为它非常清楚地表达了您的意图并且运作良好.

问题是如果你仔细观察Enumerable产品,可以使用更简单的解决方案max:

def three_greatest(list)
  list.max(3)
end

这里要学到的教训是,Enumerable库与机械工具箱不同,它拥有大量有用的工具.重要的是要花一些时间来至少阅读那里的内容,这样你就不会浪费时间重新发明已经存在于优雅形式的东西.

换句话说,在解决问题时,请检查问题是否已经解决.在许多情况下,你会发现有一种工具可以完全满足您的需求.

---

@Eric,Ruby v2.2中添加了可选参数.`min`,`min_by`和`max_by`也得到了它.

---

顺便说一下,你需要`list.max(3).last`来回答这个问题.

2> the Tin Man..：

---

只是为了帮助人们了解性能之间的差异max,sort而不是使用内置方法:

require 'fruity'

ary = (1..100).to_a.shuffle

def use_max(a)
  a.max(3).last
end

def use_sort(a)
  a.sort[-3]
end

def nth_greatest(nums, n)
  nums = nums.dup # prevent mutating the original array
  result = nil
  n.times do
    idx, max = -1, -Float::INFINITY
    nums.length.times do |i|
      idx, max = [i - 1, nums[i - 1]] if nums[i - 1] > max
    end
    result = nums.delete_at idx
  end
  result
end

compare do
  sorted { use_sort(ary) }
  maxed  { use_max(ary) }
  nth_greatested { nth_greatest(ary, 3) }
end

# >> Running each test 512 times. Test will take about 1 second.
# >> sorted is faster than maxed by 2x ± 0.1
# >> maxed is faster than nth_greatested by 3x ± 0.1

增加数组的大小:

ary = (1..1_000).to_a.shuffle

结果是:

# >> Running each test 64 times. Test will take about 1 second.
# >> maxed is faster than sorted by 80.0% ± 10.0%
# >> sorted is faster than nth_greatested by 3x ± 0.1

并再次提高阵列大小:

ary = (1..10_000).to_a.shuffle

结果是:

# >> Running each test 8 times. Test will take about 1 second.
# >> maxed is faster than sorted by 3x ± 0.1
# >> sorted is faster than nth_greatested by 2x ± 0.1

---

文档没有提到max(3)是否返回反向排序数组,即使它看起来像.

文档示例是:

a.max(2) #=> ["horse", "dog"]

这是下降,但这不是一个很好的例子,因为它更容易看到使用数字:

ary.max(3) # => [100, 99, 98]

---

以下是使用Benchmark显示基线速度的一些结果:

require 'benchmark'

ary = (1..5).to_a.shuffle

10.times do
  Benchmark.bm(4) do |b|
    b.report('sort') { ary.sort[-3] }
    b.report('max') { ary.max(3).last }
  end
end

# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000010)
# >> max    0.000000   0.000000   0.000000 (  0.000006)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000003)
# >> max    0.000000   0.000000   0.000000 (  0.000004)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000003)
# >> max    0.000000   0.000000   0.000000 (  0.000004)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000003)
# >> max    0.000000   0.000000   0.000000 (  0.000003)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000003)
# >> max    0.000000   0.000000   0.000000 (  0.000004)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000003)
# >> max    0.000000   0.000000   0.000000 (  0.000004)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000005)
# >> max    0.000000   0.000000   0.000000 (  0.000005)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000003)
# >> max    0.000000   0.000000   0.000000 (  0.000004)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000003)
# >> max    0.000000   0.000000   0.000000 (  0.000003)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000003)
# >> max    0.000000   0.000000   0.000000 (  0.000003)

并增加数组的大小:

ary = (1..100).to_a.shuffle

# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000020)
# >> max    0.000000   0.000000   0.000000 (  0.000013)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000013)
# >> max    0.000000   0.000000   0.000000 (  0.000011)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000010)
# >> max    0.000000   0.000000   0.000000 (  0.000010)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000009)
# >> max    0.000000   0.000000   0.000000 (  0.000010)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000009)
# >> max    0.000000   0.000000   0.000000 (  0.000010)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000008)
# >> max    0.000000   0.000000   0.000000 (  0.000010)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000008)
# >> max    0.000000   0.000000   0.000000 (  0.000010)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000008)
# >> max    0.000000   0.000000   0.000000 (  0.000013)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000011)
# >> max    0.000000   0.000000   0.000000 (  0.000010)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000008)
# >> max    0.000000   0.000000   0.000000 (  0.000010)

和:

ary = (1..1_000).to_a.shuffle

# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000110)
# >> max    0.000000   0.000000   0.000000 (  0.000057)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000103)
# >> max    0.000000   0.000000   0.000000 (  0.000054)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000101)
# >> max    0.000000   0.000000   0.000000 (  0.000053)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000100)
# >> max    0.000000   0.000000   0.000000 (  0.000053)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000100)
# >> max    0.000000   0.000000   0.000000 (  0.000053)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000100)
# >> max    0.000000   0.000000   0.000000 (  0.000056)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000099)
# >> max    0.000000   0.000000   0.000000 (  0.000053)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000099)
# >> max    0.000000   0.000000   0.000000 (  0.000053)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000100)
# >> max    0.000000   0.000000   0.000000 (  0.000053)
# >>            user     system      total        real
# >> sort   0.000000   0.000000   0.000000 (  0.000099)
# >> max    0.000000   0.000000   0.000000 (  0.000053)