struct Node{
    int n,idx;
    bool operator < (const Node & rhs) const
    {
        return this->n < rhs.n;
    }
    Node():n(0),idx(0){}
    Node(int _n,int _i):n(_n),idx(_i){}
};

inline int int_abs(int arg)
{
    return arg > 0? arg : -arg;
}

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        const int nums_cnt = nums.size();
        if(nums_cnt == 0)
            return false;
        if(k < 50 || nums_cnt < 1024)
            for(int i = 0; i < nums_cnt; i++)
            {
                for(int j = i + 1 ; j < i + k && j < nums_cnt; j++)
                    if(nums[i] == nums[j])
                        return true;
            }
        //return false;
        vector<Node> * vect = new vector<Node>(nums_cnt);
        for(int i = 0; i < nums_cnt; i++)
            (*vect)[i] = Node(nums[i],i);
        sort((*vect).begin(),(*vect).end());
        int strt = 0;
        int tar = (*vect)[strt].n;
        int ii,jj,dst;
        while(true)
        {
            if( strt >= nums_cnt)
                break;
            tar = (*vect)[strt].n;
            dst = strt-1;
            while((*vect)[++dst].n == tar);
            if(dst - strt > 1)
            {
                for(ii = strt; ii < dst; ii++)
                    for(jj = ii + 1; jj < dst; jj++)
                        if(int_abs((*vect)[ii].idx -(*vect)[jj].idx) <= k)
                            return true;

            }
            strt = dst;
        }
        delete vect;
        return false;
    }
};