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

My code logic to answer a programming question is:

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

1. Find the biggest number in the input array.
2. 找到输入数组中的最大数字。
3. Store that number in a new array.
4. 将该号码存储在新阵列中。
5. Delete that number from the input array.
6. 从输入数组中删除该数字。
7. Repeat #'s 1-3 until I have three elements in the new array.
8. 重复＃1-3，直到我在新数组中有三个元素。
9. Choose the last element of the array to return.
10. 选择要返回的数组的最后一个元素。

My code is returning three 10's, instead of the three largest elements in the array, 10, 8, and 4. I think it might be because once the inner while loop is done, the code cannot return back to it?

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

My test code is:

我的测试代码是：

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

My code is:

我的代码是：

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

5 个解决方案

#1

Once you start to think about solving problems like this the Ruby way, by which I mean leaning more heavily on Enumerable and expressing your intent as a series of simple operations, often chained together, then the solutions become easier to find.

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

For example, to find the three highest numbers in an arbitrary Array the obvious solution might be this:

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

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

That sorts the list, which by default is lowest to highest, and then reverses it, making it highest to lowest. The last operation is to copy out the first three entires. This seems pretty reasonable, as it expresses your intent quite clearly and works quite well.

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

The thing is if you look more closely at the Enumerable offerings there's an even easier solution using max:

问题是，如果你仔细观察Enumerable产品，那么使用max会有更简单的解决方案：

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

The lesson to learn here is that the Enumerable library, not unlike a mechanic's tool-chest, has a very large number of useful tools. It's important to take some time to at least read through what's in there so you don't end up wasting time re-inventing things that already exist in an elegant form.

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

In other words, when tackling a problem, check to see if that problems already been solved. In many cases you'll find there's a tool that does exactly what you're looking for.

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

#2

Just to help people understand the difference in performance between max, sort and not using built-in methods:

只是为了帮助人们了解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

Increasing the size of the array:

增加数组的大小：

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

results in:

结果是：

# >> 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

And bumping up the array size again:

并再次提升阵列大小：

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

results in:

结果是：

# >> 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

---

The documentation doesn't mention if max(3) returns a reversed sorted array, even though it looks like it.

文档没有提到max（3）是否返回反向排序数组，即使它看起来像。

The documentation example is:

文档示例是：

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

which is descending, but that's not a good example as it's easier to see using numbers:

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

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

---

Here are some results using Benchmark to show the baseline speeds:

以下是使用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)

And increasing the size of the array:

并增加数组的大小：

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)

And:

和：

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)

#3

You forgot to unset greatest_number

你忘了取消设置great_number

  nums.delete(greatest_number)
  three_greatest_idx += 1
  greatest_number = nil # this line
end

Obviously there is a very simple solution for this in Ruby but I took for granted that you wanted to do it on your own.

显然在Ruby中有一个非常简单的解决方案，但我理所当然地认为你想自己做。

#4

I assume this is a task where heavy usage of Enumerable module might be not permitted. There are still easier approaches all around. E.g. you do not need to maintain another array: just remove the highest from the original array N times:

我假设这是一个不允许大量使用Enumerable模块的任务。还有更简单的方法。例如。你不需要维护另一个数组：只需从原始数组中删除最高N次：

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

nth_greatest [8, 1, 10, 4], 2
#⇒ 8
nth_greatest [8, 1, 10, 4], 3
#⇒ 4

#5

Sort it and use Ruby's negative index option for arrays.

对它进行排序并使用Ruby的负数索引选项。

[8, 1, 10, 4].sort[-3]
>> 4

Edit: After many tests I have determined that the sort method shown above is faster than the method below if, when searching for the nth biggest number in an array of m elements, n > 1/20th the size of m. Since in your example we are looking for the 3rd biggest number in an array of 4 elements, and 3 is much bigger than .2, the answer above is significantly more efficient than this alternative method:

编辑：经过多次测试后，我确定上面显示的排序方法比下面的方法更快，如果在m个元素的数组中搜索第n个最大数字时，n> 1/20，大小为m。因为在你的例子中我们正在寻找4个元素数组中的第3个最大数字，而3个比.2大得多，所以上面的答案明显比这个替代方法更有效：

[8, 1, 10, 4].max(3)[-1]
>> 4