LeetCode算法题-Contains Duplicate II(Java实现)
这是悦乐书的第193次更新,第197篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第53题(顺位题号是219)。给定整数数组和整数k,找出数组中是否存在两个不同的索引i和j,使得nums [i] = nums [j]并且i和j之间的绝对差值小于等于k。例如:
输入:nums = [1,2,3,1],k = 3
输出:true
输入:nums = [1,0,1,1],k = 1
输出:true
输入:nums = [1,2,3,1,2,3],k = 2
输出:false
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
利用hashMap,依次遍历数组元素,如果当前元素不存在就put进map,如果存在,则说明具有重复元素,然后获取当前索引与此元素在map中的索引value值的绝对值,判断其是否小于等于k,如果满足,则返回true。
此解法因为用到了map.containsKey()方法,所以时间复杂度最好的情况是O(n),最坏的情况是O(n^2),空间复杂度是O(n)。
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
if (map.containsKey(nums[i]) && Math.abs(i-map.get(nums[i])) <= k) {
return true;
} else {
map.put(nums[i], i);
}
}
return false;
}
03 第二种解法
如果满足题目的条件,nums[i] = nums[j],并且j-i <= k,那么只要nums[i]等于nums[i+1]至nums[i+k]之间的任意一个,即可返回true。使用两层for循环,外层控制从1到k,内层遍历数组元素,如果外层指针加上内层指针小于数组大小,并且两指针对应的元素相等,则返回true。
此解法的时间复杂度是O(k*n),最好的情况是O(n),最坏的情况是O(n^2),空间复杂度是O(1)。此解法会超时。
public boolean containsNearbyDuplicate2(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
for (int i=1; i<= k; i++) {
for (int j=0; j<nums.length; j++) {
if (j+i < nums.length && nums[j] == nums[j+i]) {
return true;
}
}
}
return false;
}
04 第三种解法
此解法与上面第二种解法的思路一致,不过是将内外层循环换了位置,并且内层循环判断nums[i]和nums[j]相等时,对于指针的范围做了调整,从数组长度、i+1+k之间取最小值。
public boolean containsNearbyDuplicate3(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
for (int i=0;i < nums.length; i++) {
for (int j=i+1; j<Math.min(nums.length, i+1+k); j++) {
if (nums[i] == nums[j]) {
return true;
}
}
}
return false;
}
05 第四种解法
利用HashSet。此解法的代码和昨天的那道题没多大区别,只不过是在循环判断true或false的前面,加多了一个判断,如果当前的指针i大于k,那么就将HashSet中的nums[i - k - 1]元素删除,即当i>k的时候,将HashSet从第1一个元素开始移除,表示前k个元素已经不符合题目的条件了,并且随着循环继续,会依次删除不符合的元素。
public boolean containsNearbyDuplicate4(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (i > k) {
set.remove(nums[i - k - 1]);
}
if (!set.add(nums[i])) {
return true;
}
}
return false;
}
06 第五种解法
使用双指针。循环内判断true或false的地方,如果两指针不相等,并且其各自所指向的元素相等,则返回true。第二个判断是移动两个指针的关键,两个指针初始值都是0,如果两指针的差小于k,则其中做一个指针加1,否则另外一个指针加1,即判断相隔小于k位之间的元素是否相等。
public boolean containsNearbyDuplicate5(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k == 0) {
return false;
}
int p1 = 0;
int p2 = 0;
while (p1 < nums.length) {
if (nums[p1] == nums[p2] && p1 != p2) {
return true;
}
if (p2 - p1 < k && p2 < nums.length - 1) {
p2++;
} else {
p1++;
}
}
return false;
}
07 小结
算法专题目前已连续日更超过一个月,算法题文章53+篇,