Java O(n) solution


  • 0
    M

    Idea: scan from the two ends to the middle.
    Time: O(n)

    public class Solution {
        
        public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
            if(nums==null) return null;
            final int N = nums.length;
            int[] res = new int[N];
            for(int i=0, j=N-1,k=N-1; i<=j; k--){
                int y1 = calculate(nums[i],a,b,c);
                int y2 = calculate(nums[j],a,b,c);
                if(a>=0){
                    if(y1>y2){
                        res[k] = y1;
                        i++;
                    } else {
                        res[k] = y2;
                        j--;
                    }
                } else { // a<0
                    if(y1<y2){
                        res[N-1-k] = y1;
                        i++;
                    } else {
                        res[N-1-k] = y2;
                        j--;
                    }
                }
            }
            return res;
        }
        
        private int calculate (int x, int a, int b, int c){
            return a*x*x+b*x+c;
        }
        
    }
    

Log in to reply
 

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