AC java solution with quicksort


  • -1
    S
    public class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if(nums.length==0||nums.length==1) return false;
            int length=nums.length;
            int [] index=new int[length];
            for(int i=0;i<length;i++)
            index[i]=i;
            quickSort(nums,0,length-1,index);
            int stat=0;
            for(int i=1;i<length;i++)
    	 	        {
    	 	            long difValue=Math.abs((long)nums[i]-(long)nums[stat]);
    	 	            while((i!=stat)&&(difValue>t)) {stat++;difValue=Math.abs((long)nums[i]-(long)nums[stat]);}
    	 	            if(i!=stat)
    	 	            for(int j=stat;j<i;j++)
    	 	            {
    	 	            	long numsij=nums[i],numsstatj=nums[j];
    		 	            difValue=Math.abs((long)nums[i]-(long)nums[j]);
    		 	            long difindex=Math.abs((long)index[i]-(long)index[j]);
    	 	            	if((difindex<=k)&&(difValue<=t))  return true;
    	 	            }
    	 	        }
            return false;
          
        }
        void quickSort(int[] a, int low, int high,int[] ind) { 
            int p = get(a, low, high,ind);
            if(low<=(p-1))
            quickSort(a, low, p-1,ind); 
            if(high>=(p+1))
            quickSort(a, p+1, high,ind); 
    } 
    
    int get(int[] a, int low, int high,int[] ind){ 
         int compare = a[low]; 
    
         while(low < high){ 
             while(low<high && a[high]>=compare)    
                  high--; 
    
             int temp = a[low];
             int temp1=ind[low];
             a[low] = a[high];
             a[high] = temp;
             ind[low]=ind[high];
             ind[high]=temp1;
    
             while(low<high && a[low]<=compare) 
                  low++; 
    
              temp = a[low]; 
              a[low] = a[high]; 
              a[high] = temp; 
              temp1=ind[low];
              ind[low]=ind[high];
              ind[high]=temp1;
         } 
         return low;
    }
    }

Log in to reply
 

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