Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax2 + bx + c to each element x in the array.
The returned array must be in sorted order.
Expected time complexity: O(n)
Example 1:
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]
Example 2:
Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]
classSolution:defsortTransformedArray(self,nums: List[int],a:int,b:int,c:int) -> List[int]:defcal(x):return a * x **2+ b * x + c i, j, res =0,len(nums)-1, []while i <= j: p, q =cal(nums[i]),cal(nums[j])if p > q and a >0or p < q and a <=0: i +=1 res.append(p)else: j -=1 res.append(q)if a >0: res.reverse()return res
classSolution {publicint[] sortTransformedArray(int[] nums,int a,int b,int c) {int[] res =newint[nums.length];int l =0, r =nums.length-1;int index = a >0?nums.length-1:0;while (l <= r) {int left =quad(nums[l], a, b, c), right =quad(nums[r], a, b, c);if (a >0) {if (left > right) { res[index--] = left; l++; } else { res[index--] = right; r--; } } else {if (left < right) { res[index++] = left; l++; } else { res[index++] = right; r--; } } }return res; }privateintquad(int x,int a,int b,int c) {return a * x * x + b * x + c; }}