Contains Duplicate I II III

Leave a comment

November 9, 2016 by oneOokay

早上八点前起床开会的后果就是现在超级困-,=

Contains Duplicate I:

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Set. O(n)

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.

“Sliding Window” + Set 
Set.remove(obj). O(n).
Contains Duplicate III:
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
我的想法是:依旧是一个sliding window。然后需要另外一个数据结构来存一个增序和一个减序,于是想了PriorityQueue,但是写出来老错。因为审题错误!!!
nums[i]和nums[j]这两个数的差最多为t,并不等于:从nums[i]到nums[j]之前的所有数中差值最大的两个数的差值为t。
于是:sliding window:在长度为k的window中找出相差最小的两个数并且差值小于t。并不知道如何写。
一个答案是用sliding window + bucket check. bucket check是由bucket sort衍生来的,第一次看到这个bucket相关

Suppose we have consecutive buckets covering the range of nums with each bucket a width of (t+1). If there are two item with difference <= t, one of the two will happen:

(1) the two in the same bucket
(2) the two in neighbor buckets

同时复习一下confuse了我的java integer 除法运算: 1/4 = 0; 29/5 = 5; -1/5 =0; -4/5 = 0. -6/5=-1

总之这题之后变成了一个要考虑很多corner case的题以及数学题。。。
  • overflow: 用long不用int:HashMap<long, long> 跑不过我也不知道为什么,必须要用Long
  • bucket size: 用 t + 1: 防止在getId里面当t=0的时候出错
  • 当数字为负数的时候: 用number / width – 1: 防止了[-3, 3] k = 2; t = 4时 -3和3同时放到0这个bucket里面的情况。 
这里的时间复杂度是O(n)。空间复杂度是: O(min(k, n)) 

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 if (nums == null || nums.length == 0 || t < 0 || k < 0){
 return false;
 }
 HashMap<Long, Long> map = new HashMap<>();
 long width = (long)t + 1;
 for (int i = 0; i < nums.length; i ++){
 long id = getId(nums[i], width);
 if (map.containsKey(id)){
 return true;
 }
 if (map.containsKey(id + 1) && Math.abs(map.get(id + 1) - nums[i]) <= t)
 {
 return true;
 }
 if (map.containsKey(id - 1) && Math.abs(map.get(id - 1) - nums[i]) <= t){
 return true;
 }
 map.put(id, (long)nums[i]);
 if (i >= k){
 map.remove(getId(nums[i - k], width));
 }
 }
 return false;
 }
 private long getId(long number, long width){
 return number < 0 ? number / width - 1 : number / width;
 }
 还有另外一个解法用到了TreeMap,也从来没用过,明天再看吧:
Advertisements
»

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: