文章 224
评论 6
浏览 200772
Array - 220. Contains Duplicate III

Array - 220. Contains Duplicate III

220、 Contains Duplicate III

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 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

思路:

这道题是217和219的变形题,题意是说有一个整数数组,如果数组中有两个数的差在t内,并且这两个数的索引之差在k内,就返回true否则返回false。

  1. 使用暴力求解的时间复杂度是O(N*K),空间复杂度为O(1)。
  2. 使用BST来记录位置的和值可以把时间复杂度优化到O(N*logk),但是额外使用了map所以空间复杂度为O(k)。
  3. 使用bucket的思想和BST来查找最接近的值与当前值的差值,时间复杂度可以为O(n),空间的复杂度与bucket的size有关,最差就是对每一个数字都建立一个bucket。

代码:

java:

class Solution {

  /*public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

        if (nums == null || nums.length == 0 || k <= 0 || t <0) return false;
        
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long ceil = set.ceiling((long)nums[i] - t);
            Long floor = set.floor((long)nums[i] + t);
            
            if ((floor != null && floor >= nums[i]) || (ceil != null && ceil <= nums[i])) {
                return true;
            }
            
            set.add((long)nums[i]);
            if (i >= k) {
                set.remove((long)nums[i-k]);
            }
        }
        
        return false;
    }*/
    
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0) return false;
        Map<Long, Long> 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) && remappedNum - map.get(bucket - 1) <= t)
                        || (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t))
                            return true;
            if (map.entrySet().size() >= k) {
                long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
                map.remove(lastBucket);
            }
            map.put(bucket, remappedNum);
        }
        return false;
    }
}

标题:Array - 220. Contains Duplicate III
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/06/13/1560433966397.html

Nothing just happens, it's all part of a plan.

取消