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;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104186130