我有一个数字数组按升序或降序排序,我想找到插入数字的索引,同时保留数组的顺序.如果数组是[1,5,7,11,51]并且要插入的数字是9,我会期望3,所以我可以做[1,51].插入(3,9) .如果数组是[49,32,22,10,8,3,2]并且要插入的数字是9,我会期待5,所以我可以做[49,2].插入(5,9)
在保留数组排序的同时,找到在这两个数组中插入9的索引的最佳/最干净的方法是什么？
我编写了这段有用的代码,但它不是很漂亮：
array = [55,33,1] num_to_insert = 9 index_to_insert = array[0..-2].each_with_index.map do |n,index| range = [n,array[index.next]].sort index.next if num_to_insert.between?(range[0],range[1]) end.compact.first index_to_insert # => 3
解决方法
Wand Maker的回答并不错,但它有两个问题：
>它对整个数组进行排序,以确定它是升序还是降序.当你所要做的就是在比较第一个和最后一个元素来确定它之前找到一个不等于那个元素的元素时,这很愚蠢.在最坏的情况下,这是O(n)O(1)而不是O(n log n).
>当它应该使用bsearch时,它使用Array#index.我们可以进行二进制搜索,而不是遍历整个数组,因为它已经排序.在最坏的情况下,这是O(log n)而不是O(n).
我发现将它分成两种方法更清楚,但你当然可以把它变成一种：
def search_proc(ary,n)
case ary.first <=> ary.last
when 1 then ->(idx) { n > ary[idx] }
when -1 then ->(idx) { n < ary[idx] }
else raise "Array neither ascending nor descending"
end
end
def find_insert_idx(ary,n)
(0...ary.size).bsearch(&search_proc(ary,n))
end
p find_insert_idx([1,51],9)
#=> 3
p find_insert_idx([49,2],9)
#=> 5
(我在这里使用Range#bsearch.Array #bsearch的工作方式相同,但使用范围返回索引更方便,效率更高,否则我们必须执行each_with_index.to_a等.)