从排序数组到排序多项式数组的算法

Question

解决下面的问题，主要思想是，（1）如果A > 0，从两端合并，在这种情况下，两端的值比数组的中间大，（2 ) 如果 A < 0，也从两端合并，在这种情况下，两端的值比数组的中间值小。

想知道是否有更好的性能改进想法（例如时间复杂度或其他角度）、space 复杂度改进或我的代码中的任何错误？

问题,

给定一个排序的整数数组 X 和 3 个整数 A、B 和 C。Return对应的排序多项式数组。

换句话说，对数组中的每个元素 x 和 return 排序数组应用 Axx + B*x + C。

源代码在Python 2.7,

def f(v, a, b, c):
    return a*v*v + b*v + c

def sort_polynomial(numbers, a, b, c):
    result = []
    if a > 0:
        start = 0
        end = len(numbers) - 1
        while start <= end:
            if f(numbers[start], a, b, c) <= f(numbers[end], a, b, c):
                result.insert(0, (numbers[end], f(numbers[end], a, b, c)))
                end -= 1
            else:
                result.insert(0, (numbers[start], f(numbers[start], a, b, c)))
                start += 1
    elif a < 0:
        start = 0
        end = len(numbers) - 1
        while start <= end:
            if f(numbers[start], a, b, c) <= f(numbers[end], a, b, c):
                result.append((numbers[start], f(numbers[start], a, b, c)))
                start += 1
            else:
                result.append((numbers[end], f(numbers[end], a, b, c)))
                end -= 1
    else:
        raise Exception('invalid argument!')

    return result

if __name__ == "__main__":
    numbers = [-2, -1, 0, 1, 2]
    print sort_polynomial(numbers, 1, 2, 1)
    print sort_polynomial(numbers, -1, 2, 1)

Answer 1

你有功能

F(x) = A*x^2 + B * x + C

求最小值或最大值（x值-B/2A）。如果极值在您的数据范围内，则获取具有极值的索引并以合并方式从开头（如果最小）或从结尾（如果最大）填充输出数组 - 您已经实现了一种合并。

在这种情况下（初步内存分配，没有插入）复杂度是线性的O(N)

Answer 2

扩展 MBo 的优秀答案，这是一个可能的实现：

import bisect
import heapq

def f(a, b, c):
    return lambda x: a*x*x + b*x + c

def sort_polynomial(numbers, a, b, c):
    if a == 0:
        return map(f(a, b, c), numbers)              # No x^2 term? Just map!
    apex = -b / ( 2 * a )                            # Find min or max
    middle_index = bisect.bisect_left(numbers, apex) # Where to cut list in half
    numbers = map(f(a, b, c), numbers)               # Apply f
    l1 = numbers[0:middle_index]                     # Part before apex
    l2 = numbers[middle_index:]                      # Part after apex
    if a < 0:
        l2.reverse()                                 # Revert after apex
    else:
        l1.reverse()                                 # Revert before apex
    return list(heapq.merge(l1, l2))                 # Merge and return

if __name__ == "__main__":
    numbers = [-2, -1, 0, 1, 2]
    print sort_polynomial(numbers, 0, 2, 1)
    print sort_polynomial(numbers, 1, 0, 0)
    print sort_polynomial(numbers, 1, 2, 1)
    print sort_polynomial(numbers, -1, 2, 1)

从排序数组到排序多项式数组的算法

algorithm from sorted array to sorted polynomial array

python

sorting

algorithm

polynomial-math

python-2.7