C++ solution with stable sort


  • 0
    E

    Haven't seen this solution here. The idea is simple: keep index with every element and use stable sort to preserve original ordering of equal elements.

    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            if(nums.size()<=1 || k == 0)
                return false;
            vector<pair<int,int>> ni(nums.size());
            for(int i=0; i < nums.size(); ++i)
            {
                ni[i] = make_pair(nums[i],i);
            }
            stable_sort(ni.begin(), ni.end(), [](const pair<int,int>&l, const pair<int,int>&r)->int{return l.first < r.first;});
            for(int i=0; i < ni.size()-1; ++i)
            {
                if(ni[i].first == ni[i+1].first && ni[i+1].second - ni[i].second <= 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.