C++ solution 24ms with O(N) time and O(K) space by using set


  • 2
    A
    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            int size = nums.size();
            int maxElements = k + 1;
            // the difference between first and last element is at most k
            if (size <= maxElements)
            {
                set<int> s(nums.begin(), nums.end());
                return s.size() != size;
            }
            
            set<int> s(nums.begin(), nums.begin() + maxElements);
            for (int i = maxElements; i < size; i++)
            {
                if (s.size() != maxElements)
                    return true;
                
                s.erase(nums[i - maxElements]);
                s.insert(nums[i]);
            }
            return s.size() != maxElements;
        }
    };
    
    1. Using a set to determine if any element repeats.
    2. For example, nums = { 1, 2, 3, 1, 3 } and k = 2
    3. Add all elements with index <= k to set s = { 1, 2, 3 }, and start for loop from k + 1 to the end of nums
    4. erase num[0] from set s and insert num[k + 1] to s, s = { 2, 3, 1 }
    5. erase num[1] from set s and insert num[k + 2] to s, s = { 3, 1 }
    6. If the size of set s is less than k + 1 at any step, it indicates duplicate items.

  • 0

    Thanks for giving the answer!

    But I dont think the time would be O(N) because you cannot guarantee that the time of a K size set insert and erase element is O(1).

    Infact I thik your time should be O(N*log(k)). As far as i know , the STL set inster or erase an element with size k should be logk .


Log in to reply
 

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