首页 > 其他 > 详细

leetcode 220 Contains Duplicate - zerteen

时间:2020-03-07 11:41:09      阅读:46      评论:0      收藏:0      [点我收藏+]

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

1
2
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

1
2
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

  • 使用hashmap来保存t个数
  • 将每个数模(t+1),将其放入对应的bucket中,那么每个bucket中的number的index差可定是在0-t之间的。
  • 对于相邻的两个bucket,也可能存在index差在0-t的number,一次,对于每个相邻的bucket,需要检查是否index差小于t
  • nums[i]可能是负数,若负数模(t+1),对应的bucket会错位,因此,nums[i]需要将其全部转换为正数,即nums[i]-Integer.MIN_VALUE;
  • 控制hashmap的item数目,来保证所求的index距离小于等于k
  • Corner case是k<1 || t < 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class  大专栏  leetcode 220 Contains Duplicate - zerteenpan>{
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
HashMap<Long, Long> m = new HashMap<>();
if ( k < 1 || t < 0)
return false;
for (int i=0; i<nums.length; i++) {
long mapped = (long)nums[i] - Integer.MIN_VALUE;
long bucket = mapped/((long)t+1);
if (m.containsKey(bucket)) {
return true;
}
if (m.containsKey(bucket-1) && (mapped - m.get(bucket-1)) <= t) {
return true;
}
if (m.containsKey(bucket+1) && (m.get(bucket+1) - mapped) <= t) {
return true;
}
if (i >= k) {
m.remove(((long)nums[i-k]-Integer.MIN_VALUE)/((long)t+1));
}
m.put(bucket, mapped);
}
return false;
}
}




leetcode 220 Contains Duplicate - zerteen

原文:https://www.cnblogs.com/lijianming180/p/12433000.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!