国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Contains Duplicate III

MageekChiu / 766人閱讀

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

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://m.specialneedsforspecialkids.com/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 評論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 評論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 評論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 評論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 評論0 收藏0

發表評論

0條評論

MageekChiu

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<