C++ solution with stable sort

  • 0

    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 {
        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.