leetcode 220. Contains Duplicate III

秒速五厘米 2021-12-13 19:45 193阅读 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 条评论，193人围观）

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

相关阅读

相关 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 赞/ 97 阅读

相关 leetcode217. contains duplicate

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

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

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

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

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

相关 LeetCode-Contains Duplicate II

Problem: > > Given an array of integers and an integer k, find out whether there are

待我称王封你为后i/ 2022年08月09日 05:09/ 0 赞/ 4 阅读

相关 LeetCode-Contains Duplicate 217

Problem： > > Given an array of integers, find if the array contains any duplicates.

谁借莪１个温暖的怀抱￠/ 2022年08月09日 05:08/ 0 赞/ 2 阅读

相关 [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 赞/ 189 阅读

相关 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 赞/ 147 阅读

相关 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 赞/ 151 阅读

相关 leetcode Contains Duplicate

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

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

相关 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 赞/ 194 阅读