arrays - Ruby:插入和排序数字

Question

我必须在 Ruby 中创建一个方法来插入一个数字并对结果列表进行排序。

输入如下:

insert_number([2.0,3.5,4.8], 4.1) 

应该输出:

[2.0,3.5,4.1,4.8]

输入如下:

insert_number([], 5.1) 

它应该输出:

[5.1]

这是我不完整的代码:

def insert_number(list, number)
  new_list = []               
  position = 0                         
  number_has_been_inserted = false     # Remember whether a new number 
  # has been inserted.
  while position < list.length 
    position += 1
    new_list = list + [number] 
    ...
  end
  ...
    new_list
end

print insert_number([2.0,3.5,4.8], 4.1)

Answer 1

bsearch only works if the original input array is already sorted, which is not a pre-condition. – @pjs

考虑到您的原始数组已排序，您可以在此处使用二进制搜索。它会执行得更好，因为它不需要对每个插入执行昂贵的排序过程。

这个改变了原始数组

def insert_number(arr, num)
  i = (0...arr.size).bsearch{ |a| arr[a] > num }
  i ||= arr.size
  arr.insert(i, num)
end

arr = []
insert_number(arr, 1)
#=> [1]
insert_number(arr, 2)
# => [1, 2]
insert_number(arr, 2.1)
# => [1, 2, 2.1]
insert_number(arr, 1.3)
#=> [1, 1.3, 2, 2.1]

每次调用都会返回新的数组

def insert_number(arr, num)
  i = (0...arr.size).bsearch{ |a| arr[a] > num }
  i ||= arr.size
  arr[0, i] + [num] + arr[i..-1]
  # or
  # arr.dup.insert(i, num)
end

arr = []
arr = insert_number(arr, 1)
#=> [1]
arr = insert_number(arr, 2)
# => [1, 2]
arr = insert_number(arr, 2.1)
# => [1, 2, 2.1]
arr = insert_number(arr, 1.3)
#=> [1, 1.3, 2, 2.1]

附言:

Recent Ruby versions have bsearch_index – @Stefan