FXTi's blog
0%

contains-duplicate-ii

Posted on Edited on

Contains Duplicate II – LeetCode 219

Problem

Description

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 absolute difference between i and j is at most k.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(k == 0) return false;
        set<int> s;
        for(unsigned i = 0; i != nums.size(); ++i){
            if(s.count(nums[i]) == 0){
                if(s.size() == k)
                    s.erase(nums[i-k]);
                s.insert(nums[i]);
            } else {
                return true;
            }
        }
        return false;
    }
};

思路

使用一个Set维护的滑动窗口来保存所需的信息，时间复杂度$O(n)$，空间复杂度$O(k)$。
耗时$32$ ms，排名$77.79\%$

Better

思路

使用Vector来保存所需信息，使用sort处理。用空间换时间，优势在于较少的额外数据结构维护开销。时间复杂度$O(nlog_{2}{n})$，空间复杂度$O(n)$。
耗时$19$ ms，排名$99.68\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        vector<pair<int, int>> v;
        if (nums.size() == 0) {
            return false;
        }
        for (int i = 0; i < (int) nums.size(); i++) {
            v.push_back(make_pair(nums[i], i));
        }
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size() - 1; i++) {
            if (v[i].first == v[i + 1].first && (v[i + 1].second - v[i].second) <= k) {
                return true;
            }
        }
        
        return false;
    }
};