我必须在 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)
最佳答案
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
关于arrays - Ruby:插入和排序数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40775169/