Есть ли лучший способ найти местоположение минимального элемента в массиве?

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-ish. Спасибо.

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 

Answer 2

Это стандартный алгоритм поиска минимального элемента в массиве, он может быть лучше, если массив уже будет отсортирован до вызова этой функции.

В противном случае я не могу найти более эффективный способ сделать это. В частности, лучшее время, которое мы можем сделать, - это линейное время в большой нотации O.

Answer 3

Если это не просто академический вопрос, почему бы просто не использовать собственный метод Ruby's sort? Он реализован с использованием алгоритма быстрой сортировки и считается довольно быстрым.

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

Answer 4

В основном это лучшее, что вы можете сделать, если вы можете написать его немного более лаконично:

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

Answer 5

Существует более простой способ, и это работает для меня в рубине 1.9.2:

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