Leetcode: Contains Duplicate II

By | 2016 年 5 月 11 日

Question

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.

Analyze

It’s strait forward to using dictionary on this question. First run, save position of each number in the dictionary; Second run, check the dictionary to see if there is another duplication in this array and check the position of it.
But there is a situation that need take into consideration, that the array may contain the duplication multiple times. To deal with this, just checking in the first run, to see if the last position (if any) is close enough.

Code

C++ code

class Solution {
public:
    inline int abs(int v) {
        return v < 0 ? -v : v;
    }
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> dict;
        for(int i=0; i<nums.size(); ++i) {
            if(dict.find(nums[i]) != dict.end()) {
                if(abs(dict[nums[i]]-i) <= k)
                    return true;
            }
            dict[nums[i]]=i;
        }
        for(int j=0; j<nums.size(); ++j){
            map<int,int>::iterator it = dict.find(nums[j]);
            map<int,int>::iterator endit = dict.end();
            if(endit != it){
                int i = it->second;
                if(i != j && abs(i-j) <= k)
                    return true;
            }
        }
        return false;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注