My 8ms Java solution beats 98.8%


  • 0
    X

    The basic idea is to sort the array, and record each element's index in original array. Since I want to practice quick sort so I implemented the modified version of quick sort manually.

    nums[] will be a sorted array, and indexs[] will be the array recording the original position of each element.
    eg.
    the input is 3,1,5,6
    nums: 1, 3, 5, 6 (after sort)
    indexs: 1, 0, 2, 3
    so we can easily use a for-loop to check whether two element's value and index are within the given input;

    public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    int n = nums.length;
    int[] indexs = new int[n];
    for(int i = 0; i < n; i++){
    indexs[i] = i;
    }
    quicksort(nums, indexs, 0, n - 1);

        for(int i = 0; i < n; i++){
            int start = nums[i];
            int sindex = indexs[i];
            for(int j = i + 1; j < n; j++){
                int end = nums[j];
                int eindex = indexs[j];
                long diff = (long)end - (long)start;
                if(diff > t){
                    break;
                }
                if(Math.abs(eindex - sindex) <= k){
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private void quicksort(int[] nums, int[] indexs, int start, int end){
        if(start >= end){
            return;
        }
        int mid = start + (end - start)/2;
        int pivot = nums[mid];
        int i = start;
        int j = end;
        while(i <= j){
            while(nums[i] < pivot){
                i++;
            }
            while(nums[j] > pivot){
                j--;
            }
            if(i <= j){
                if(nums[i] != nums[j]){
                    swap(nums, indexs, i, j);
                }
                i++;
                j--;
            }
        }
        quicksort(nums, indexs, start, i - 1);
        quicksort(nums, indexs, i, end);
    }
    
    private void swap(int[] nums, int[] indexs, int i, int j){
        int value = nums[i];
        nums[i] = nums[j];
        nums[j] = value;
        int index = indexs[i];
        indexs[i] = indexs[j];
        indexs[j] = index;
    }
    

    }


Log in to reply
 

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