X

曜彤.手记

随记,关于互联网技术、产品与创业

  1. 219. Contains Duplicate II:

LeetCode 每日一题 - 219. Contains Duplicate II

LeetCode 每日一题系列,今天第四题。这道题与之前的 “217.Contains Duplicate” 基础解法思路大体相似,不过在判断是否含有重复元素的同时,还需要保证元素的索引信息不能够丢失。【Array】【HashTable】

219. Contains Duplicate II

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

Example:

Given nums = [2, 7, 11, 15, 11],
Given k = 2,

Because nums contains duplicate number 11, and the distance between two duplicates less or equal than k,
So after your function it should return true.
Else return false.

1. 最基本的方法,还是遍历:

两个指针,指针 i 指向当前元素,指针 j 指向 i 其后的任意元素。最内层循环依次比较指针 i指针 j 对应元素大小,外层循环将指针 i 向后移动,直到找到相等值并判断此时指针 i指针 j 的相对位置是否小于等于 k。时间复杂度 “O(n2)”。代码如下所示:

public static boolean containsDuplicate(int[] nums) {
  int arrLen = nums.length;
  for (int i = 0; i< arrLen; i++) {
    for (int j = i + 1; j < arrLen; j++) {
      if (nums[i] == nums[j] && j - i <= k)
      return true;
    }
  }
  return false;
}

2. 优化的方法,同样使用HashMap:

思路不变,先检查 HashMap 中是否含有此元素,如果有则检查当前元素与该元素的索引距离是否大于 k,如果没有则将该元素放入 HashMap,并继续从数组中取下一个元素,否则返回 false 。时间复杂度 “O(n)“。代码如下所示:

public static boolean containsDuplicateOptimize(int[] nums) {
  int arrLen = nums.length;
  Map<Integer, Integer> map = new HashMap<>();
  int prevPos = 0;
  
  for (int i = 0; i< arrLen; i++) {
    if (map.containsKey(nums[i])) {
      prevPos = map.get(nums[i]);
      if((i - prevPos) <= k)
        return true;
      else 
        return false;
    } else {
      map.put(nums[i], i);
    }
  }
  return false;    
}

3. 更加优化的方法,使用 Set 集合来保持一个固定大小的检测窗口:

这里我们使用 Set 来保持一个大小为 k 的检测窗口,只要在这个窗口中含有重复的元素,则一定满足两个元素之间的距离小于 k 的条件。代码如下所示:

public static boolean containsDuplicateOptimizeFurther(int[] nums) {
  Set<Integer> set = new HashSet<Integer>();  
  // 定义窗口的首尾指针;
  int start = 0, end = 0;
  // 开始遍历;
  for (int i = 0; i < nums.length; i++) {   
    if (!set.contains(nums[i])) {  
      set.add(nums[i]);   
      end++;   // 如果 Set 中没有此元素则加入,尾指针后移;
    } else { 
      return true;   // 有则返回 true;
    }
    
    // 保持首尾指针距离不大于 k;
    if(end - start > k) {  
      set.remove(nums[start]);  //如果大于则移除首指针元素;
      start++;   // 移除后首指针后移;
    }  
  }  
  return false;
}



评论 | Comments


Loading ...