[LintCode/LeetCode] Contains Duplicate III

MageekChiu 發(fā)布于2019-08-19 10:48 / 761人閱讀

Problem

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example

Given nums = [1,3,1], k = 1, t = 1, return false.

Solution Brute force

public class Solution {
    /**
     * @param nums: the given array
     * @param k: the given k
     * @param t: the given t
     * @return: whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // Write your code here
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (Math.abs(j-i) <= k && Math.abs(nums[i]-nums[j]) <= t) return true;
            }
        }
        return false;
    }
}

Maintain a size k window

public class Solution {
    /**
     * @param nums: the given array
     * @param k: the given k
     * @param t: the given t
     * @return: whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // Write your code here
        if (k < 1 || t < 0) return false;
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long reMappedNum = (long)nums[i] - Integer.MIN_VALUE;
            long bucket = reMappedNum / ((long)t + 1);
            if (map.containsKey(bucket) ||
              (map.containsKey(bucket-1) && Math.abs(reMappedNum - map.get(bucket-1)) <= t) ||
              (map.containsKey(bucket+1) && Math.abs(reMappedNum - map.get(bucket+1)) <= t)) {
                return true;    
            }
            if (i >= k) {
                long lastBucket = ((long)nums[i-k] - Integer.MIN_VALUE) / ((long)t + 1);
                map.remove(lastBucket);
            }
            map.put(bucket, reMappedNum);
        }
        return false;
    }
}