O(n) python solution by using the property of quadratic function


  • 0
    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]
            """
            res = []
            if a != 0:
                axis = -float(b) / (float(a) * 2)
                for i in range(len(nums)):
                    if axis >= nums[i - 1] and axis < nums[i]:
                        p, q = i - 1, i
                        break
                while p >= 0 and q < len(nums):
                    if axis - nums[p] < nums[q] - axis:
                        res.append(a * pow(nums[p], 2) + b * nums[p] + c)
                        p -= 1
                    else:
                        res.append(a * pow(nums[q], 2) + b * nums[q] + c)
                        q += 1
                while p >= 0:
                    res.append(a * pow(nums[p], 2) + b * nums[p] + c)
                    p -= 1
                while q < len(nums):
                    res.append(a * pow(nums[q], 2) + b * nums[q] + c)
                    q += 1
                return res if a > 0 else res[::-1]
            else:
                for num in nums:
                    res.append(a * pow(num, 2) + b * num + c)
                return res if b > 0 else res[::-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.