220 Contains Duplicate III 存在重复 III
2024-09-04 15:16:31
给定一个整数数组,判断数组中是否有两个不同的索引 i 和 j,使 nums [i] 和 nums [j] 的绝对差值最大为 t,并且 i 和 j 之间的绝对差值最大为 k。
详见:https://leetcode.com/problems/contains-duplicate-iii/description/
Java实现:
TreeSet数据结构(Java)使用红黑树实现,是平衡二叉树的一种。
该数据结构支持如下操作:
floor()方法返set中≤给定元素的最大元素;如果不存在这样的元素,则返回 null。
ceiling()方法返回set中≥给定元素的最小元素;如果不存在这样的元素,则返回 null。
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
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;
}
}
参考:https://www.cnblogs.com/jiajiaxingxing/p/4572871.html
https://www.jianshu.com/p/3e27c6fe284e
C++实现:
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int size=nums.size();
if(size==0||nums.empty())
{
return false;
}
map<long long,int> m;
int j=0;
for(int i=0;i<size;++i)
{
if(i-j>k)
{
m.erase(nums[j++]);
}
auto idx=m.lower_bound((long long)nums[i]-t);
if(idx!=m.end()&&abs(idx->first-nums[i])<=t)
{
return true;
}
m[nums[i]]=i;
}
return false;
}
};
最新文章
- Python正则表达式:最短匹配
- ElasticSearch学习问题记录——Invalid shift value in prefixCoded bytes (is encoded value really an INT?)
- UIWebView 与 JS 交互(1):Objective-C 调用 Javascript
- Javascript数组,String对象,Math对象,Date对象,正则表达式
- C# 从Excel2003将数据导入到SQL2005,数据发生截断的问题分析
- java开发中获取路径的一些方式
- linux下高可用LVS搭建及配置方法
- 含隐变量模型求解——EM算法
- Dynamics CRM模拟OAuth请求获得Token后在外部调用Web API
- LOJ6089 小Y的背包计数问题(根号优化背包)
- GSON中Java对象与JSON互相转换——(一)
- [NOSQL] Redis介绍
- [转]An Intuitive Explanation of Convolutional Neural Networks
- 牛客网Java刷题知识点float数据在内存中是怎么存储的
- 第2章 如何安装KEIL5
- C++11 explicit的使用
- java并发编程:线程安全管理类--原子操作类--AtomicLongArray
- 使用CADisplayLink写秒表
- Android音视频点/直播模块开发实践总结-zz
- 兰亭集势收购美国社交购物网站Ador,收购的是人才
热门文章
- 读书笔记-HBase in Action-第二部分Advanced concepts-(3)非Javaclient
- instancetype VS id
- Python练习题2
- poj 2585 Window Pains 暴力枚举排列
- GCC 编译详解 (转)
- Entity Framework工具POCO Code First Generator的使用(参考链接:https://github.com/sjh37/EntityFramework-Reverse-POCO-Code-First-Generator)
- ios开发--NSDate与NSDateFormatter的相关用法【转】
- ASP.NET MVC 原理
- iOS开发——高级篇——iOS涂鸦画板效果实现
- UVALive3126 Taxi Cab Scheme —— 最小路径覆盖