360. Sort Transformed Array

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]

二元一次方程，对方程求导得到顶点。
x0=-b/(2*a)

如果array 全部在x0的一边，那么相当于单调递增或者单调递减的一次方程

假设a>0

如果不在一边，那么距离x0越远的那个值是最大，不会有比它更大的（two pointer）。就是array的两端，找最远的那个点。（因为如果是最近那个点x1无法判断那个点的位置，因为可能最远的点往中间走的时候会有比x1更近的点）

因此a>0的时候，先填最大值位置。a < 0的时候，先填最小值位置。（先放的意思是距离远）

a==0时候，vertex 是最左边点。距离最远的一定是最右边的点。
那么就是b<0, 先填最小；b>0,先填最大。

 public class Solution {  
   public int[] sortTransformedArray(int[] nums, int a, int b, int c) {  
     double vertex = a== 0 ? 0 : -(double)b/(2*a);  
     int[] ans = new int[nums.length];  
     int i = 0, j = nums.length-1;  
     int k = a > 0 ? nums.length-1 : 0 , dir =a > 0? -1:1;  
     if(a==0){  
       k = b>=0?nums.length-1 : 0 ;  
       dir =b >= 0? -1:1;          
     }  
     while(i <= j){  
       if(a==0 ||Math.abs(nums[j] - vertex) >= Math.abs(nums[i] - vertex)){  
         ans[k] = a*nums[j]*nums[j] + b*nums[j--] + c;  
       }else{  
         ans[k] = a*nums[i]*nums[i] + b*nums[i++] + c;  
       }  
       k = k + dir;  
     }  
     return ans;  
   }  
 }