Sort Transformed Array

这道题一开始就陷入了陷阱，执着的认为是一道纯双指针的题，后来就发现没有任何办法在没有指导规律的情况下把一个数组在O(n)时间内转为排序数组，所以与其说这是一道双指针的题，不如说是一道纯数学题，因为这里的双指针处理没有一点难度，主要就在于发现题目描述里面的a大于零，等于零，小于零时函数的规律，比如当a大于零时，二次函数是有一个最小值的，所以我们可以基于原数组的两边设置对撞指针然后比较两个值谁更大然后加到结果数组的最后面，相反小于零时则加到最前面，a等于零时数组就是一个单调递增或递减的一次函数了，下面是代码，写的不太精简，但是情况分类比较清楚

class Solution(object):
    def sortTransformedArray(self, nums, a, b, c):
        """
        :type nums: List[int]
        :type a: int
        :type b: int
        :type c: int
        :rtype: List[int]
        """
        result = []
        func = lambda x: a * (x ** 2) + b * x + c
        start, end = 0, len(nums) - 1

        if a < 0:
            while start <= end:
                left, right = func(nums[start]), func(nums[end])
                if left < right:
                    result.append(left)
                    start += 1
                else:
                    result.append(right)
                    end -= 1
            return result

        while start <= end:
            left, right = func(nums[start]), func(nums[end])
            if left > right:
                result = [left] + result
                start += 1
            else:
                result = [right] + result
                end -= 1

        return result