Quite straight forward solution in Java, with comments


  • 0
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
            if(nums.length == 0 || nums == null) return new int[0];
            
            int[] res = new int[nums.length];
            //if a == 0, there will be no square number;
            if(a == 0){
                if(b < 0){
                    for(int i = 0; i < nums.length; i ++){
                        res[nums.length - 1 - i] = b * nums[i] + c;
                    }
                }else if(b > 0){
                    for(int i = 0; i < nums.length; i ++){
                        res[i] = b * nums[i] + c;
                    }
                }else{
                    for(int i = 0; i < nums.length; i ++){
                        res[i] = c;
                    }
                }
                return res;
            }
            
            //calculating the symmetric axis
            double axis = -0.5 * ((double)b / (double)a);
            //use binary search to find the index which is most closet to the axis
            int index = -1;
            int low = 0, high = nums.length - 1;
            while(low < high){
                int mid = low + (high - low) / 2;
                if(nums[mid] == axis){
                    index = mid;
                    break;
                }else if(nums[mid] < axis){
                    low = mid + 1;
                }else{
                    high = mid;
                }
            }
            
            if(index == -1){
                index = Math.abs(nums[low - 1] - axis) <= Math.abs(nums[low] - axis) ? low - 1 : low;
            }
            
            //use two pointers to keep recording the current index and its adjcent index, keep moving the index and adding values
            int pre = index - 1, post = index + 1;
            for(int i = 0; i < nums.length; i ++){
                System.out.print("index = " + index + " ");
                int tmp = a * nums[index] * nums[index] + b * nums[index] + c;
                if(a < 0){
                    res[nums.length - 1 - i] = tmp;
                }else{
                    res[i] = tmp;
                }
                if(pre < 0){
                    index = post;
                }else if(post >= nums.length){
                    index = pre;
                }else{
                    index = Math.abs((double)(nums[pre] - axis)) <= Math.abs((double)(nums[post] - axis)) ? pre : post;
                }
                if(index == pre) pre = pre - 1;
                if(index == post) post = post + 1;
            }
            return res;
        }
    

Log in to reply
 

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