大佬教程收集整理的这篇文章主要介绍了ruby – 将数字插入有序数组中,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
在保留数组排序的同时,找到在这两个数组中插入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
>它对整个数组进行排序,以确定它是升序还是降序.当你所要做的就是在比较第一个和最后一个元素来确定它之前找到一个不等于那个元素的元素时,这很愚蠢.在最坏的情况下,这是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等.)
以上是大佬教程为你收集整理的ruby – 将数字插入有序数组中全部内容,希望文章能够帮你解决ruby – 将数字插入有序数组中所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。