Java O(n) solution using Binary Search


  • -1

    If a is not 0, we know it's polynomial function, and we wan't to find the global extreme value(the peak value or the valley value, depending on the sign of a); to find peak or valley,we first use Binary Search to find the element in the array which is closest to -b/2a, let's say the index of the element returned from binary search is i,then we use two pointers p1=i-1,p2=i+1, compare nums[p1] and nums[p2], decide which is closer to -b/2a, and move two pointers until both of them are out of index range;if a<0, the iteration of two pointers are outputing elements in descending order(we need to reverse result),if a>0, the output are in acsending order.

    if a is 0, we look at b, and this is a linear function; we output element by just iterating nums in array

     public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
    	int[] res=new int[nums.length];
    	int index=0;
    	if(a!=0){
    		double val=-(double)b/(2*(double)a);
    		int k=bianrySearch(0,nums.length-1,val,nums);
    		int i=0;
    		int j=0;
    		if(k>=0&&k<nums.length&&nums[k]==val){
    			res[index]=compute(k,nums,a,b,c);
    			index++;
    			i=k-1;
    			j=k+1;
    		}else{
    			i=k-1;
    			j=k;
    		}
    	
    		while(i>=0||j<nums.length){
    			if(i>=0&&j<nums.length){
    				if(Math.abs(nums[i]-val)<Math.abs(nums[j]-val)){
    					res[index]=compute(i,nums,a,b,c);
    					i--;
    				}else{
    					res[index]=compute(j,nums,a,b,c);
    					j++;
    				}
    			}else if(i>=0){
    				res[index]=compute(i,nums,a,b,c);
    				i--;
    			}else{	
    				res[index]=compute(j,nums,a,b,c);
    				j++;
    			}
    			index++;
    		}
    
    		if(a<0){
    			reverse(res);
    		}
    	}else{
    		if(b<0){
    			for(int i=nums.length-1;i>=0;i--){
    				res[nums.length-1-i]=compute(i,nums,a,b,c);
    			}
    		}else{
    			for(int i=0;i<nums.length;i++){
    				res[i]=compute(i,nums,a,b,c);
    			}
    		}
    	}
    	return res;
    }
    
    public int bianrySearch(int start,int end,double target,int[] nums){
    	int i=start;
    	int j=end;
    	while(i<=j){
    		int mid=(i+j)/2;
    		if(nums[mid]==target){
    			return mid;
    		}else if(nums[mid]<target){
    			i=mid+1;
    		}else{
    			j=mid-1;
    		}
    	}
    	return i;
    }
    
    public int compute(int i,int[] nums,int a,int b,int c){
    	return a*nums[i]*nums[i]+b*nums[i]+c;
    }
    
    public void reverse(int[] nums){
    	int i=0;
    	int j=nums.length-1;
    	while(i<j){
    		int tmp=nums[i];
    		nums[i]=nums[j];
    		nums[j]=tmp;
    		i++;
    		j--;
    	}
    }
    

    }


  • 0
    Z

    The thing is, you don't need to find the one which is closest to -b/2a. You can just put the two pointer at two ends of the array and let them go towards each other and meet at -b/2a.


  • 0

    Try finding first which one is furthest to -b/2a, which is much easier: bound to be at either end.


Log in to reply
 

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