[LeetCode]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 difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

题目大意:

给定一个整数数组,判断其中是否存在两个不同的下标i和j满足:| nums[i] - nums[j] | <= t 并且 | i - j | <= k

解题思路:

解法I:“滑动窗口” + 字典(桶)

如果: | nums[i] - nums[j] | <= t   式a

等价: | nums[i] / t - nums[j] / t | <= 1   式b

推出: | floor(nums[i] / t) - floor(nums[j] / t) | <= 1   式c

​等价: floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 式d

其中式b是式c的充分非必要条件,因为逆否命题与原命题等价,所以:

如果: floor(nums[j] / t) ∉ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 非d

推出: | nums[i] - nums[j] | > t   非a

因此只需要维护一个大小为k的窗口(字典)numDict,其中键为nums[i] / t,值为nums[i]。

遍历数组nums时,检查nums[i]与键集{floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1}对应的值的差值即可。

Python代码:

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @param {integer} t
    # @return {boolean}
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if k < 1 or t < 0:
            return False
        numDict = collections.OrderedDict()
        for x in range(len(nums)):
            key = nums[x] / max(1, t)
            for m in (key, key - 1, key + 1):
                if m in numDict and abs(nums[x] - numDict[m]) <= t:
                    return True
            numDict[key] = nums[x]
            if x >=  k:
                numDict.popitem(last=False)
        return False

解法II:“滑动窗口” + TreeSet

参考LeetCode Discuss:https://leetcode.com/discuss/38177/java-o-n-lg-k-solution

TreeSet数据结构(Java)使用红黑树实现,是平衡二叉树的一种。

该数据结构支持如下操作:

1. floor()方法返set中≤给定元素的最大元素;如果不存在这样的元素,则返回 null。

2. ceiling()方法返回set中≥给定元素的最小元素;如果不存在这样的元素,则返回 null。

Java代码:

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(k < 1 || t < 0)
            return false;
        TreeSet<Integer> set = new TreeSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            int n = nums[i];
            if(set.floor(n) != null && n <= t + set.floor(n) || 
                    set.ceiling(n) != null && set.ceiling(n) <= t + n)
                return true;
            set.add(n);
            if (i >= k)
                set.remove(nums[i - k]);
        }
        return false;
    }
}

 

本文链接:http://bookshadow.com/weblog/2015/06/03/leetcode-contains-duplicate-iii/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. Shenghang Shenghang 发布于 2015年7月19日 06:41 #

    百度的广告太影响网站观感了. 动来动去分心的厉害. 而且不能像Google AdSense一样把没必要的广告停掉.

  2. 在线疯狂 在线疯狂 发布于 2015年7月21日 15:11 #

    挂联盟广告是想冲抵一点网站运营成本,我考虑把广告的位置换一下,看看会不会好一些

  3. Shenghang Shenghang 发布于 2015年7月22日 02:12 #

    也许应该换成其他平台的广告?作为一个码农,我看到的Google平台广告都是云服务以及编程有关的生产力工具。但是百度的广告却莫名其妙,根本不感兴趣。也可能是因为我从来不用百度搜索,所以百度只能给我一些烂广告了。

  4. 在线疯狂 在线疯狂 发布于 2015年7月22日 19:54 #

    我试着申请一下Google Adsense,看来百度联盟的广告与内容匹配程度不太高,不知道Banner广告和右侧的方形广告哪一个显得更碍眼一些?

  5. Shenghang Shenghang 发布于 2015年7月23日 00:28 #

    主要是广告内容与视觉感受和博客内容太不搭了,放哪都一样。除了google,还可以考虑一下淘宝和Amazon的推荐广告。这两个不是很懂,不太确定一定有。但是我在其他网站看到过淘宝和Amazon根据我的浏览历史生成的推荐广告。

  6. 李叔叔敏感词 李叔叔敏感词 发布于 2015年11月17日 09:29 #

    请问python方法的time complexity 是多少呢 谢谢

  7. 李叔叔敏感词 李叔叔敏感词 发布于 2015年11月17日 09:29 #

    O(nk)么

  8. 在线疯狂 在线疯狂 发布于 2015年11月17日 16:18 #

    是的,n为nums的长度

  9. 熹儿 熹儿 发布于 2015年11月27日 19:29 #

    python那个代码用这个例子:
    nums=[10,2,40,3,60,4]
    k=4
    t=3
    返回值是false呢,应该是true吧

  10. 在线疯狂 在线疯狂 发布于 2015年11月27日 20:20 #

    试了一下,运行结果是True

  11. 熹儿 熹儿 发布于 2015年11月28日 10:09 #

    果然 我换了个环境运行一下就是true了 不好意思哦

  12. 伟龙 伟龙 发布于 2016年1月15日 17:16 #

    第一种方法中,不同的nums[i]有可能计算出同样的key值吧,如果他们在一个窗口中,后者不就覆盖前者了么..这样会不会出错...

  13. 在线疯狂 在线疯狂 发布于 2016年1月15日 18:21 #

    循环末尾的语句 if x >= k: numDict.popitem(last=False),会将下标之差超出k的元素从字典中移除。

  14. E E 发布于 2016年2月29日 07:16 #

    adblock

  15. 书影网友 书影网友 发布于 2017年9月3日 07:54 #

    试了,返回值是true

张贴您的评论