b*****3 发帖数: 39 | 1 Given a sorted list of integer - list, and three integer params a, b, c,
provide ax^2 + bx + c for each x in list in sorted order. | w********m 发帖数: 1137 | 2 binary search找离-b/2a最近的点, 向左向右两个pointer | H*M 发帖数: 22 | | b*******w 发帖数: 56 | 4
Cool.
【在 w********m 的大作中提到】 : binary search找离-b/2a最近的点, 向左向右两个pointer
| b*******w 发帖数: 56 | 5 def sort_by_quadratic_poly(nums, a, b, _):
pivot = -(b/(a*2.0))
index_right = bisect.bisect_left(nums, pivot)
sorted_by_quadratic_poly = []
index_left = index_right - 1
while index_left >=0 and index_right < len(nums):
if abs(nums[index_left] - pivot) <= abs(nums[index_right] - pivot):
sorted_by_quadratic_poly.append(nums[index_left])
index_left -= 1
else:
sorted_by_quadratic_poly.append(nums[index_right])
index_right += 1
if index_left < 0:
sorted_by_quadratic_poly.extend(nums[index_right:])
else:
sorted_by_quadratic_poly.extend(nums[:(index_left + 1)])
return sorted_by_quadratic_poly | z**m 发帖数: 3080 | 6 这个有很多bug。
【在 b*******w 的大作中提到】 : def sort_by_quadratic_poly(nums, a, b, _): : pivot = -(b/(a*2.0)) : index_right = bisect.bisect_left(nums, pivot) : sorted_by_quadratic_poly = [] : index_left = index_right - 1 : : while index_left >=0 and index_right < len(nums): : if abs(nums[index_left] - pivot) <= abs(nums[index_right] - pivot): : sorted_by_quadratic_poly.append(nums[index_left]) : index_left -= 1
| h******v 发帖数: 36 | 7 多用点space。
def sortys(arr, a, b, c):
from bisect import bisect_left as bl
ys = [a*x**x+b*x+c for x in arr]
x0 = -b/2/a
ri = bl(ys, a*x0**x0+b*x0+c)
li = ri -1
_ys = []
while li >= 0 and ri < len(arr):
if ys[li] <= ys[ri]:
_ys.append(ys[li]); li -= 1
else:
_ys.append(ys[ri]); ri += 1
_ys.extend(reversed(arr[:li+1]))
_ys.extend(arr[ri:]))
return _ys
【在 w********m 的大作中提到】 : binary search找离-b/2a最近的点, 向左向右两个pointer
| z*******o 发帖数: 4773 | | g**4 发帖数: 863 | |
|