Why my O(n) cpp solution with map is so slow?


  • 0
    Z

    This is my solution and It takes 80ms but If I use sort which is a nlogn solution It will be much faster

    class Solution {
    public:
    	bool containsNearbyDuplicate(vector<int>& nums, int k) {
    		if (nums.size() <= 1 || k <= 0) return false;
    		map<int, int> hash;
    		for (int i = 0; i < nums.size(); i++) {
    			if (hash.find(nums[i]) == hash.end())
    				hash[nums[i]] = i;
    			else if (i-hash[nums[i]] <= k)
    				return true;
    			else hash[nums[i]] = i;
    		}
    		return false;
    
    	}
    };

  • 1
    B

    Maybe you can try unordered_map.


  • 1
    B

    Because map used red black trees due to which all operations on map takes O(logn ) time.


  • 0
    Z

    thanks a lot! that is the point !


  • 0
    Z

    Yes! I understand that a few days later ,after I ask this question ,thx!


Log in to reply
 

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