share my O(n) java solution!


  • 0
    C
    
    public class Solution {
        public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
            int[] res = new int[nums.length];
            float middle = -b/(float)(2*a);
            
            int mid=(int)middle;
            int index=Arrays.binarySearch(nums,mid);
            if(index<0) index=-(index+1);
        
            int i=index-1;
            int j=index;
            int p=a>=0 ? 0:nums.length-1;
            int count=a>=0?1:-1;
            while(i>=0&&j<nums.length){
                if(Math.abs(nums[i]-middle)>=Math.abs(nums[j]-middle)){
                    res[p]=a*nums[j]*nums[j]+b*nums[j]+c;
                    j++;
                    p+=count;
                }else{
                    res[p]=a*nums[i]*nums[i]+b*nums[i]+c;
                     i--;
                     p+=count;
                }
            }
            while(i>=0){
                res[p]=a*nums[i]*nums[i]+b*nums[i]+c;
                i--;
                p+=count;
            }
            while(j<nums.length){
                res[p]=a*nums[j]*nums[j]+b*nums[j]+c;
                j++;
                p+=count;
            }
            return res;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.