CONY的世界

360. Sort Transformed Array

注意這題之所以變難是因為O(n)，因為不能用sorting，不然會變成O(nlogn)

用到的概念是數學的概念拋物線

對稱軸是 x=-b/2a，所以根據a>0與否決定拋物線是向上還是向下，然後依照距離對稱軸的距離來排序出來的y值

另外要注意a=0的情況要獨立出來討論

class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int l=0,r=0;
double middlepoint = -b/(2*((double)a));
boolean positive;
if(a != 0) {
for(int index=0;index<nums.length-1;index++){
if(nums[index] <= middlepoint && nums[index+1] > middlepoint){
l=index; r=index+1;
break;
}
}
positive = (a>0)?true:false;
} else
positive = (b>0)?true:false;

int[] result = new int[nums.length];
for(int i=0; i < nums.length; i++) {
int x=0;
if(a != 0) {
if(l < 0 || (r < nums.length && (Math.abs(nums[r]-middlepoint) < Math.abs(nums[l]-middlepoint))))
x=nums[r++];
else
x=nums[l--];
} else
x=nums[i];
if(positive)
result[i] = a*x*x+b*x+c;
else
result[nums.length-i-1] = a*x*x+b*x+c;
}
return result;
}
}

更漂亮的做法是這個，用到拋物線的概念

a>=0  兩邊一定大於等於中間點大

a<0 兩邊小於等於中間點

用 two pointer 把所有點掃過一遍

不用考慮a=0時b的狀況，因為會比較y值才寫入sorted array 所以兩種都行

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] sorted = new int[n];
        int i=0, j= n-1;
        int index= (a>=0)?n-1:0;
        while(i<=j){
            if(a>=0)
                sorted[index--] = (quad(nums[i],a,b,c) > quad(nums[j],a,b,c))?quad(nums[i++],a,b,c):quad(nums[j--],a,b,c); 
            else
                sorted[index++] = (quad(nums[i],a,b,c) < quad(nums[j],a,b,c))?quad(nums[i++],a,b,c):quad(nums[j--],a,b,c);
        }
        return sorted;
    }
    int quad(int x,int a, int b, int c){
        return a*x*x+b*x+c;
    }
}