ruby – 将数字插入有序数组中

发布时间：2020-12-16 23:27:35 所属栏目：百科来源：网络整理

导读：我有一个数字数组按升序或降序排序,我想找到插入数字的索引,同时保留数组的顺序.如果数组是[1,5,7,11,51]并且要插入的数字是9,我会期望3,所以我可以做[1,51].插入(3,9) .如果数组是[49,32,22,10,8,3,2]并且要插入的数字是9,我会期待5,所以我可以做[49,2].插

我有一个数字数组按升序或降序排序,我想找到插入数字的索引,同时保留数组的顺序.如果数组是[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等.)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!