Java O(n) solution


  • 0
    Z

    public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {

        int i, n = nums.length, j, temp;
        int[] ans = new int[n];
        
        if(a == 0) {
            if(b > 0) {
                for(i=0;i<n;i++) {
                    ans[i] = b*nums[i] + c;
                }
            } else {
                
                for(i=0;i<n;i++) {
                    ans[i] = b*nums[n-1-i] + c;
                }
            }
            
            return ans;
        }
        
        double mid = -((double)b)/(2*a);
        
        if(a > 0) {
            double[] dis = new double[n];
            int minDis = 0;
            
            for(i=0;i<n;i++) {
                dis[i] = Math.abs(nums[i] - mid);
                if(dis[i] < dis[minDis]) {
                    minDis = i;
                }
            }
            
            int[] order = new int[n];
            order[0] = minDis;
            int cur = 1, left = minDis - 1, right = minDis + 1, num;
            
            while(left >= 0 && right < n) {
                if(dis[left] < dis[right]) {
                    order[cur++] = left;
                    left--;
                } else {
                    order[cur++] = right;
                    right++;
                }
            }
            
            while(left >= 0) {
                order[cur++] = left--;
            }
            
            while(right < n) {
                order[cur++] = right++;
            }
            
            for(i=0;i<n;i++) {
                num = nums[order[i]];
                ans[i] = a * num * num + b * num + c;
            }
            
            return ans;
            
        } else {
            nums = sortTransformedArray(nums,-a,-b,-c);
            
            for(i=0;i<n;i++) {
                ans[i] = -nums[n-1-i];
            }
            
            return ans;
        }
    }
    

    }


Log in to reply
 

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