360. Sort Transformed Array -------M

 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]

A:

就是找对称轴。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

class Solution { public: vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) { if(a<0){ auto res = sortTransformedArray(nums,-a,-b,-c); reverse(res.begin(), res.end()); for(auto& t : res) // NEED to get the inverse t *= -1; return res; } if(a==0){ vector<int> res = nums; if(b<0) reverse(res.begin(), res.end()); for(auto& t : res) t = t* b+c; return res; } // now we ,have a>0 double axis = - double(b) / (2*a); // NEED USE DOUBLE, INT would be wrong // linearly find the index that's smaller th deque<int> before; int i=0; while(i<nums.size() && nums[i] <= axis){ before.push_front(a* nums[i] * nums[i] + b * nums[i] + c); i++; } vector<int> after; while(i<nums.size()){ after.push_back(a* nums[i] * nums[i] + b * nums[i] + c); i++; } // merge two list vector<int> res; auto it1 = before.begin(); auto it2 = after.begin(); while(it1!= before.end() || it2 != after.end()){ if(it1 == before.end()){ res.push_back(*it2); it2++; }else if(it2 == after.end()){ res.push_back(*it1); it1++; }else{ if( *it1 <= *it2){ res.push_back(*it1); it1++; }else{ res.push_back(*it2); it2++; } } } return res; } };

Mistakes:

对称轴需要用double类型。 如果用 int , 会遇到边界问题。