220. Contains Duplicate III

Description

Intuition

TreeSet Solution

上一个TreeSet，丝毫不僵硬

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
      final TreeSet<Integer> visited = new TreeSet<>();
      for (int i = 0; i < nums.length; i++) {
        if (i - k - 1 >= 0) {
          visited.remove(nums[i - k - 1]);
        }
        // determine if it's visited
        final Integer max = visited.ceiling(nums[i]), min = visited.floor(nums[i]);
        if ((max != null && (long) max - nums[i] <= t)
            || (min != null && (long) (nums[i]) - min <= t)) {
          return true;
        }
        visited.add(nums[i]);
      }
      return false;
    }

Bucket Sort Solution

如果每间隔t建立一个bucket，那么我们只需要从左到右扫描一遍，看看bucket里是否已经有元素，如果有，那么就是有duplicate

但是当t == 0时这里有个很大的问题，divided by zero. Check the wrong solution.

小技巧是使用t + 1作为bucket size，然后检查本身以及前后的bucket里是否有元素

Pitfall

两个数相减会integer overflow

 @Test
  void testFailed2() throws Exception {
    final int[] input = new int[]{-1, 2147483647};
    Assertions.assertFalse(solution.containsNearbyAlmostDuplicate(input, 1, 2147483647));
  }

Solution

Bucket Wrong Solution

  public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if (nums == null || nums.length == 0 || k <= 0 || t < 0) {
      return false;
    }
    int min = nums[0], max = nums[0];
    for (int i = 1; i < nums.length; i++) {
      min = Math.min(min, nums[i]);
      max = Math.max(max, nums[i]);
    }

    // create buckets
    final List<Set<Integer>> buckets = new ArrayList<>();
    final int bucketNum = (int) (((long) max - min) / t) + 1;
    for (int i = 0; i < bucketNum; i++) {
      buckets.add(new HashSet<>());
    }

    for (int i = 0; i < nums.length; i++) {
      if (i - k - 1 >= 0) {
        final int becketIndex = getBucketIndex(nums[i - k - 1], min, t);
        buckets.get(becketIndex).remove(nums[i - k - 1]);
      }

      final int bucketIndex = getBucketIndex(nums[i], min, t);
      final Set<Integer> bucket = buckets.get(bucketIndex);
      if (!bucket.isEmpty()) {
        return true;
      } // end of if
      bucket.add(nums[i]);
    }
    return false;
  }

  private static int getBucketIndex(final int num, final int min, final int t) {
    return (int) (((long) num - min) / t);
  }

Reference

results matching ""

    No results matching ""