Ugly code...but it works fast


  • 5
    Z
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        //trivial reject
        if (nums.length < 2) return false;
        if (k == 0 || t < 0) return false;
        
        int max = nums[0];
        int min = nums[0];
        
        for (int i : nums)
        {
            max = Math.max(i, max);
            min = Math.min(i, min);
        }
        
        // trivial accept
        if (max == min) return true;
        
        double temp = t;
        temp++;
        
        int length = (int)Math.ceil(((double)max-min)/temp) + 1;
        int[][] table = new int[3][length];
        
        for (int i = 0; i < nums.length; i++)
        {
            int num = nums[i];
            int place =(int) (((double)num - min)/temp);
            
            if (table[0][place] != 0)
                if (table[1][place] + k >= i)
                    return true;
            if (place > 0 && table[0][place - 1] == 1 && table[1][place - 1] + k >= i && table[2][place - 1] + t >= num)
                    return true;
            else if (place < length - 1 && table[0][place + 1] == 1 && table[1][place + 1] + k >= i && table[2][place + 1] - t <= num)
                    return true;
            
            table[0][place] = 1;
            table[1][place] = i;
            table[2][place] = num;
        }
        return false;
    }
    

  • 0
    D

    Extremely well designed code !


  • 1
    Q

    I think there are some problems with this code, you may test:
    [7,2,8]
    2
    1


  • 0

    @qyang Thanks, I have just added this test case.


  • 0
    Z

    @qyang Yes, thank you! Actually this is a huge mistake. I have fixed it, but I don't know how to edit the post...


  • 0

    @zhidou You can edit the post by clicking on the three dots icon (right side of your post), and click "Edit".


  • 0
    Z

    @1337c0d3r Thank you very much!


Log in to reply
 

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