Contains Duplicate III

Posted on   |   In   |  

给定一个整数数组，判断其中是否存在两个不同的下标i和j满足：| num s[i] - nums[j] | <= t 并且 | i - j | <= k

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.

题目的意思是:给定一个整数数组，判断其中是否存在两个不同的下标i和j满足：| nums[i] - nums[j] | <= t 并且 | i - j | <= k
基本方法:使用双重循环，但是会超时

1
2
3
4
5
6
7
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        for(int i = 0; i< nums.size(); ++i)
            for(int j = i + 1; j <= i + k && j < nums.size(); ++j)
                if(abs(nums[i] - nums[j]) <= t) return true; 
};

解法二，利用二叉查找树(用map和set都可以)
| nums[i] - nums[j] | <= t 并且 | i - j | <= k;
此处只考虑了(1)nums[i] - t这种情况，没有考虑(2)nums[i] + t这种情况。即[nums[i] - t, nums[i] + t]在使用lower_bound的过程中，得到的是nums[i] - iter的最小迭代器，这个区间也包括nums[i] + t，所以需要测试所得的iter是否为myset.end(),并且要满足iter - nums[i]<=t; 在这里需要注意的是下面的代码并不能满足条件

1
2
3
4
auto iter1 = myset.lower_bound(nums[i] - t);
auto iter2 = myset.lower_bound(nums[i] + t);
if( (iter1 != myset.end() && nums[i] - *iter1 <= t) || (iter2 != myset.end() && *iter2 - nums[i] <= t)) 
            return true;

因为报错

1
2
3
4
5
6
7
8
Input:
[1,2]
1
-1
Output:
true
Expected:
false

仔细想了想在这里要求的是t>0,k >=1 的，上面的这种情况不是一种正确的测试用例

1
2
3
4
5
6
7
8
Input:
[4,2]
2
1
Output:
true
Expected:
false

这种情况就是一种很典型的情况，在遍历2的时候，得到差值是-2，它是小于1的(实际上，这时候的差值应该按2来计算)，实际上这种情况不满足

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<int>  myset;
        
        for(size_t i = 0; i < nums.size(); ++i){
            auto iter = myset.lower_bound(nums[i] - t);
            if(iter != myset.end() && *iter - nums[i] <= t) return true;
            //此处可能担心重复的问题，没有问题，因为始终保持在大小为k的窗口(即使发生了覆盖)
            myset.insert(nums[i]);
            //索引的差值最大为k，那么set的size最大为k+1
            if(myset.size() > k) myset.erase(nums[i - k]);
        }
        return false;
    }
};

利用桶排序时间复杂度O(n)
具体的分析见:http://bookshadow.com/weblog/2015/06/03/leetcode-contains-duplicate-iii/

如果： | nums[i] - nums[j] | <= t   式a
等价： | nums[i] / t - nums[j] / t | <= 1   式b
推出： | floor(nums[i] / t) - floor(nums[j] / t) | <= 1   式c
等价： floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 式d

其中式b是式c的充分非必要条件，因为逆否命题与原命题等价，所以：

如果： floor(nums[j] / t) ∉ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 非d
推出： | nums[i] - nums[j] | > t   非a

因此只需要维护一个大小为k的窗口（字典）numDict，其中键为nums[i] /t，值为nums[i]。

摘自http://bookshadow.com/weblog/2015/06/03/leetcode-contains-duplicate-iii/
一点需要注意的是当nums[i]为负数的情况

1
2
---|---|---|---|---|---|---|---|---|---|---|---|--
  -4  -3  -2  -1   0   1   2   3   4   5   6

这样测试用例-3, 3落在同一个桶中，负数的时候求取的num[i]/t - 1来避免这种情况
Input:
[-3,3]
2
4
Output:
true
Expected:
false

还有一点需要注意的是除数为t不合适,这样当测试案例为[1, 1] k = 1, t = 0时,会出现溢出(除以0)，有两种方法，
(1)选取t+1,这是需要主要的是防止t+1溢出，要用long long保存，否则会溢出
Input:
[-1,2147483647]
1
2147483647(INT_MAX)
Output:
true
Expected:
false

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        if (n < 2 || k < 1 || t < 0){
            return false;
        }

        unordered_map<long long, long long> buckets;
        long long width = (long long)t + 1;
        for (int i = 0; i < n; i++)
        {
            long long id = getBucketId(nums[i], width);

            // found the value in the same bucket
            if (buckets.find(id) != buckets.end())
            {
                return true;
            }

            // found the value in the adjacent bucket
            if ((buckets.find(id - 1) != buckets.end() && nums[i] - buckets[id - 1] < width) ||
                (buckets.find(id + 1) != buckets.end() && buckets[id + 1] - nums[i] < width))
            {
                return true;
            }

            // insert current value to buckets
            buckets[id] = nums[i];

            if (i >= k)    // remove out of range element
            {
                buckets.erase(getBucketId(nums[i - k], width));
            }
        }

        return false;
    }
private:
    long long getBucketId(long long i, long long w) {
        return i < 0 ? (i + 1) / w - 1 : i / w;
    }
};

(2)单独处理t= 0的情况，当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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        size_t n = nums.size();
        if(n < 2 || k < 1 || t < 0)
            return false;
            
        unordered_map<int, int> buckets;
        int width = t;
        //t为0的情况
        if(t == 0){
            for(size_t i = 0; i < n; ++i){
                if(buckets.find(nums[i]) != buckets.end() )
                    return true;
                buckets[nums[i]] = i;
                
                if( i >= k)
                    buckets.erase(nums[i - k]);
            }
            return false;
        }
        
        //t不为0的情况
        for(size_t i = 0; i < n; ++i){
            int key = getBucketId( nums[i], width );
            
            if(buckets.find(key) != buckets.end() )
                return true;
            if(buckets.find(key - 1) != buckets.end() && nums[i] - buckets[key - 1] <= t ||
                buckets.find(key + 1) != buckets.end() && buckets[key + 1] - nums[i] <= t)
                return true;
            
            buckets[ key ] = nums[i];
            
            if( i >= k)
                buckets.erase(getBucketId(nums[i - k], width));
        }
        return false;
    }
private:
    int getBucketId(int num, int w){
        return num < 0?num/w - 1:num/w;
    }
};