20 ms hybrid solution, brute force if k is small, otherwise sort, n*k or n*log(n) complexity


  • 0
    Q
    class Solution {
        struct myNode{ int val, ind; };
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            if(nums.size()<2) return false;
            if(k<=12) {
                for(int i=k,j,val;i<nums.size();++i) {
                    for(val=nums[i], j=i-k;nums[j]!=val;++j) {}
                    if(j<i) return true;
                }
                auto pend=nums.begin()+std::min(k,(int)nums.size());
                std::sort(nums.begin(),pend);
                return std::adjacent_find(nums.begin(),pend)!=pend;
            }
            vector<myNode> num_and_ind(nums.size());
            for(int i=0;i<nums.size();++i) {
                num_and_ind[i].val=nums[i];
                num_and_ind[i].ind=i;
            }
            std::sort(num_and_ind.begin(),num_and_ind.end(),[](const myNode lhs,const myNode rhs) { return lhs.val<rhs.val || lhs.val==rhs.val && lhs.ind<rhs.ind; });
            auto p=&num_and_ind[0], pend=&num_and_ind[num_and_ind.size()];
            for(auto next=p+1;next!=pend;++p,++next) {
                if(p->val==next->val && next->ind-p->ind<=k) return true;
            }
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.