将数字插入有序数组中

Question

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

9在保留数组排序的同时,找到插入这两个数组中的任何一个的索引的最佳/最干净的方法是什么？

我编写了这段有用的代码,但它不是很漂亮:

array = [55, 33, 10, 7, 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

Answer 1

Wand Maker 的答案还不错，但有两个问题：

1. 它对整个数组进行排序以确定是升序还是降序。当你所要做的就是找到一个不等于它之前的元素比较第一个和最后一个元素以确定这一点。那是在）​​ 最坏情况下的O (1) 而不是O ( n log n )。

2. 该Array#index用的时候就用bsearch。我们可以进行二分搜索，而不是迭代整个数组，因为它是排序的。最坏情况下的时间复杂度为 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, 5, 7, 11, 51], 9)
#=> 3

p find_insert_idx([49, 32, 22, 11, 10, 8, 3, 2], 9)
#=> 5

（我Range#bsearch在这里使用。Array#bsearch工作原理相同，但使用范围返回索引更方便，而且效率更高，因为否则我们必须做each_with_index.to_a一些事情。）