Given a sorted array of integers nums and integer values a, b and c. Apply a 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:
nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,
Result: [3, 9, 15, 33]
nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5
Result: [-23, -5, 1, 7]
思路：因为是排好序的数组，我们用两个指针从数组两边向中间计算答案。根据每次计算的函数值的大小决定移动哪个指针。复杂度O(N)。
1 class Solution {
2 public:
3 int f(int x, int a, int b, int c) {
4 return a * x * x + b * x + c;
5 }
6 vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
7 int len = nums.size();
8 vector<int> res(len);
9 int left = 0, right = nums.size() - 1, count = 0;
10 while (left <= right) {
11 int leftRes = f(nums[left], a, b, c);
12 int rightRes = f(nums[right], a, b, c);
13 bool goLeft = (a >= 0 && leftRes >= rightRes) || (a < 0 && leftRes <= rightRes);
14 int curPos = (a >= 0 ? len - 1 - count : count);
15 if (goLeft) {
16 res[curPos] = leftRes;
17 left++;
18 } else {
19 res[curPos] = rightRes;
20 right--;
21 }
22 count++;
23 }
24 return res;
25 }
26 };