推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 每天一个开发小知识 > 281.LeetCode | 220. 存在重复元素 III

281.LeetCode | 220. 存在重复元素 III

每天一个开发小知识 2021-04-20

每天一个开发小知识


01


题目

在整数数组 nums 中,是否存在两个下标 i 和 j


使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t


且满足 i 和 j 的差的绝对值也小于等于 ķ


如果存在则返回 true,不存在返回 false


02

思路

set 的底层实现是红黑树

查找,插入,删除的时间复杂度均为 O(logn)

因此

这题我们可以巧用数据结构 - set

用 set 保存一个可变的 k 个元素(滑动窗口,窗口大小为 k)

并且利用 set 自身接口 lower_bound 获取关键元素

// lower_bound 返回第一个大于等于 key 的元素的迭代器set<long> s;set<long>::iterator iter = s.lower_bound(key)

03

解法:巧用数据结构 - set

时间复杂度 O(n * logk),空间复杂度 O(k)

class Solution {public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { set<long> s;
for (int i = 0; i < nums.size(); ++i) { auto iter = s.lower_bound(long(nums[i]) - t); if (s.end() != iter && *iter <= (long(nums[i]) + t)) { return true; }
s.insert(nums[i]); if (k < s.size()) { s.erase(nums[i - k]); } }
return false; }};

每天一个开发小知识,今天你学废了吗?

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《281.LeetCode | 220. 存在重复元素 III》的版权归原作者「每天一个开发小知识」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注每天一个开发小知识微信公众号

每天一个开发小知识微信公众号:code-soldier

每天一个开发小知识

手机扫描上方二维码即可关注每天一个开发小知识微信公众号

每天一个开发小知识最新文章

精品公众号随机推荐