leetcode 220. Contains Duplicate III

秒速五厘米 2021-12-13 19:45 173阅读 0赞

Compared with contains duplicate II, we should record a sorted set within the length k window.  
So when we visit a new value, we can get the floor and ceiling of this value, if value - floor <= t or ceiling - value <= t, then return true.  
And before the code we can have a review on some retrieve methods in NavigableSet

E lower(E e) means less than or null  
E floor(E e) means less equal or null  
E higher(E e) means bigger than or null  
E ceiling(E e) means bigger equal or null

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

转载于:https://www.cnblogs.com/exhausttolive/p/10667990.html

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 220. Contains Duplicate III | 220. 存在重复元素 III （Treeset解法+分桶解法）

题目 [https://leetcode.com/problems/contains-duplicate-iii/][https_leetcode.com_problem

女爷i/ 2022年10月07日 09:59/ 0 赞/ 76 阅读

相关 leetcode217. contains duplicate

leetcode217. Contains Duplicate Given an array of integers, find if the array contain

缺乏、安全感/ 2022年09月25日 06:30/ 0 赞/ 127 阅读

相关 Contains Duplicate III（C++存在重复元素 III）

（1）滑动窗口 class Solution { public: bool containsNearbyAlmostDuplicate(

今天药忘吃喽~/ 2022年09月03日 04:25/ 0 赞/ 122 阅读

相关 [leetcode]: 217. Contains Duplicate

1.题目描述 Given an array of integers, find if the array contains any duplicates. Your fu

蔚落/ 2022年06月16日 03:44/ 0 赞/ 164 阅读

相关 leetcode 220. Contains Duplicate III TreeSet和SortedSet的应用 + C++的lower_bound的应用 + 移动窗口

Given an array of integers, find out whether there are two distinct indices i and j in t

亦凉/ 2022年06月08日 10:16/ 0 赞/ 128 阅读

相关 LeetCode217. Contains Duplicate解题

大家好，我又回来了，隔了一个星期没有刷题了在这一个星期我想了很多，Java虽然上手容易，用着也很顺手，我目前最熟悉的也还是Java，但是Java语言的设计局限了它不能做很

朱雀/ 2022年06月06日 05:19/ 0 赞/ 157 阅读

相关 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in t

古城微笑少年丶/ 2022年05月29日 03:27/ 0 赞/ 126 阅读

相关 leetcode Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function sho

红太狼/ 2021年12月18日 14:43/ 0 赞/ 180 阅读

相关 leetcode 219. Contains Duplicate II

Keep a window of width k, before visit new element, remove nums\[i - k - 1\]. Other de

╰半夏微凉°/ 2021年12月13日 19:47/ 0 赞/ 185 阅读

相关 leetcode 220. Contains Duplicate III

Compared with contains duplicate II, we should record a sorted set within the length k w

秒速五厘米/ 2021年12月13日 19:45/ 0 赞/ 174 阅读