2ms Java O(n) solution using simple Math and two pointers


  • 0
    A
    1. Find the extremum point
    2. scan the array to left and right using two pointers starting from extremum point
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        if(nums == null || nums.length == 0){
            return new int[0];
        }
        int[] res = new int[nums.length];
        if(a == 0){
            for(int i = 0; i < nums.length; ++i){
                int index = b < 0 ? nums.length - i - 1 : i;
                res[index] = nums[i] * b + c;
            }
            return res;
        }
        double midVal = -(b / (2.0 * a)); //extremum
        int midIndex = binarySearch(nums, midVal); //Find extremum's index
        int delta = a > 0 ? 1 : -1; //Two cases, a > 0 or a < 0
        int index = a > 0 ? 0 : nums.length - 1;
        
        int left = midIndex - 1;
        int right = midIndex;
        while(left >= 0 || right < nums.length){
            double disLeft = left < 0 ? Double.MAX_VALUE : midVal - nums[left]; //Handle boundary case
            double disRight = right >= nums.length ? Double.MAX_VALUE : nums[right] - midVal;
            if(disLeft < disRight){
                res[index] = transfer(nums[left], a, b, c);
                --left;
            }else{
                res[index] = transfer(nums[right], a, b, c);
                ++right;
            }
            index += delta;
        }
        return res;
    }
    
    private int transfer(int num, int a, int b, int c){
        return a * num * num + b * num + c;
    }
    
    private int binarySearch(int[] nums, double midVal){
        int low = 0;
        int high = nums.length;
        while(low < high){
            int mid = low + (high - low) / 2;
            if(nums[mid] == midVal){
                return mid;
            }else if(nums[mid] > midVal){
                high = mid;
            }else{
                low = mid + 1;
            }
        }
        return low;
    }

Log in to reply
 

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