[LintCode/LeetCode] Contains Duplicate III

MageekChiu 发布于2019-08-19 10:48 / 648人阅读

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;
    }
}

GPU服务器私有云 Contains DUPLICATE III ucos-iii 消息队列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76466.html

[LintCode/LeetCode] Contains Duplicate II

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

894974231 2019-08-19 10:48 评论0 收藏0
[LintCode/LeetCode] Remove Duplicate Letters

Problem Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical...

wanghui 2019-08-15 18:01 评论0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0
[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不过这道题里仍要注意两个细节。中，为时，返回长度为的空数组建立结果数组时，是包括根节点的情况，是不包含根节点的情况。而非按左右子树来进行划分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 评论0 收藏0
[LintCode/LeetCode] Single Number III

摘要：去掉最后一个保留最后一个保留最后一个保留第一个这道题在论坛里参考了和两位仁兄的解法。思想是将中所有的数进行异或运算。不同的两个数异或的结果，一定至少有一位为。最后，将和存入数组，返回。 Problem Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2...

lanffy 2019-08-14 15:33 评论0 收藏0