有没有更好的方法来查找数组中最小元素的位置？

Question

现在我有

def min(array,starting,ending)
  minimum = starting
  for i in starting+1 ..ending
    if array[i]<array[minimum]
      minimum = i
    end    
  end

return minimum
end

有没有更好的 Ruby 实现方式？这个看起来还是有点像 C 语言风格。谢谢。

- unj2

---

你所说的“更好”是指更高效还是需要更少的代码行数？ - Rahul

抱歉，我是指在 Ruby 中有更好的实现方式。 - unj2

Answer 1

如果你想要查找最小元素的索引，可以使用 Enumerable#enum_for 获取一组元素-索引对的数组，然后使用 Enumerable#min 查找其中的最小值（这也将是原始数组中的最小值）。

% irb
irb> require 'enumerator'
#=> true
irb> array = %w{ the quick brown fox jumped over the lazy dog }
#=> ["the", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog"]
irb> array.enum_for(:each_with_index).min
#=> ["brown", 2]

如果你想将它绑定到特定的数组下标：

irb> start = 3
#=> 3
irb> stop = 7
#=> 7
irb> array[start..stop].enum_for(:each_with_index).min
#=> ["fox", 0]
irb> array[start..stop].enum_for(:each_with_index).min.last + start
#=> 3

- rampion

Answer 2

基本上这就是你能做的最好的了，不过你可以更简洁地写出来：

def minval(arr)
    arr.inject {|acc,x| (acc && acc < x ? acc : x)}
end

- Ana Betts

---

我认为OP想要最小值的索引，而不是值本身。这使得使用inject有点困难。 - Matthew Schinckel

而且，你甚至不需要使用除了 arr.min 以外的任何东西来获取最小值。 - Matthew Schinckel

虽然这很聪明，但我不能使用它。 - unj2

Answer 3

有一种更简单的方法，适用于我的ruby 1.9.2：

a = [6, 9, 5, 3, 0, 6]
a.find_index a.min

- Prajjwal

Answer 4

这是在数组中查找最小元素的标准算法，如果在调用此函数之前已经对数组进行了排序，则可以更好地优化。

否则，我找不到更有效的方法。具体来说，在大O符号表示的线性时间内是我们能做到的最好的。

- AlbertoPL

---

对不起，我的意思是在Ruby中是否有更好的实现相同的算法？ - unj2

Answer 5

如果这不仅仅是一个学术问题，为什么不直接使用Ruby的本地sort方法呢？它使用快速排序算法实现，并被认为非常快。

a = [3, 4, 5, 1, 7, 5]
a.sort![0] # => 1

- Bryan M.

---

在“大型”列表上，这将会更加昂贵。时间复杂度为O(n*log(n))而不是O(n)。 - Bill Lynch

时间增加了很多倍，我无法将子程序集成到像Selection_Sort这样的另一个方法中。 - unj2

同意。我觉得似乎需要进行一次排序。 - Bryan M.