leetcode360. 有序转化数组-蒲公英云

leetcode360. 有序转化数组

给你一个已经排好序的整数数组 nums 和整数 a、b、c。对于数组中的每一个数 x，计算函数值 f(x) = ax2 + bx + c，请将函数值产生的数组返回。

要注意，返回的这个数组必须按照升序排列，并且我们所期望的解法时间复杂度为 O(n)。

示例 1：

输入: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
输出: [3,9,15,33]
示例 2：

输入: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
输出: [-23,-5,1,7]

思路：

先判断是否为二次函数。

如果是，再判断开口的上下，根据和对称轴点的距离来判断函数值的大小，走双指针的逻辑。

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int len=nums.length;
        int[] ans=new int[len];
        if(a==0){
            if(b>0){
                for(int i=0;i<len;i++){
                    ans[i]=b*nums[i]+c;
                }
            }else{
                for(int i=0;i<len;i++){
                    ans[i]=b*nums[len-i-1]+c;
                }
            }
        }else if(a>0){
            double mid = -b * 1.0 / a / 2;
            int start=0;
            int end=len-1;
            int index=len-1;
            while(start<=end){
                if(Math.abs(mid-nums[start])>Math.abs(mid-nums[end])){
                    ans[index--]=a*nums[start]*nums[start]+b*nums[start]+c;
                    start++;
                }else{
                    ans[index--]=a*nums[end]*nums[end]+b*nums[end]+c;
                    end--;
                }
            }
        }else{
            double mid = -b * 1.0 / a / 2;
            int start=0;
            int end=len-1;
            int index=0;
            while(start<=end){
                if(Math.abs(mid-nums[start])>Math.abs(mid-nums[end])){
                    ans[index++]=a*nums[start]*nums[start]+b*nums[start]+c;
                    start++;
                }else{
                    ans[index++]=a*nums[end]*nums[end]+b*nums[end]+c;
                    end--;
                }
            }
        }
        return ans;
    }
}