Do not understand why my C++ code does not work.


  • 0
    M

    I use the following code

    class Solution {
    public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
    
    	if (nums.empty()) return false;
    	if (k == 0) return false;
    
    	if (nums.size() - 1 <= k){
    		unordered_set<int> storage;
    		for (int i = 0; i <= k; i++){
    			if (!storage.insert(nums[i]).second) return true;
    		}
    	}
    
    	if (nums.size() - 1 > k){
    		unordered_set<int> storage;
    		for (int i = 0; i <= k; i++){
    			if (!storage.insert(nums[i]).second) return true;
    		}
    		unordered_set<int>::iterator it;
    		for (int i = k + 1; i<nums.size(); i++){
    			it = storage.begin();
    			storage.erase(it);
    			if (!storage.insert(nums[i]).second) return true;
    		}
    	}
    	return false;
    }};
    

    Then after submitting my answer it showed wrong answer for the test [1,2,1], k=1. However, when I use the same code and same inputs on my computer, I got the right answer. Any reason for this situation?


  • 1
    L

    First, when nums.size() - 1 > k, you use for (int i = 0; i <= k; i++). I think k here is out of range for the array.
    Then,

    for (int i = k + 1; i<nums.size(); i++){
            it = storage.begin();
            storage.erase(it);
            if (!storage.insert(nums[i]).second) return true;
       }
    

    using this, how can you guarantee the distance between two equal numbers is at most k?
    Maybe I am wrong, but in my opinion, Set is not a queue or vector, we can not assume that the oldest item will be at the begin() of the set all the time?


  • 0
    M

    Maybe you are right that the oldest item will not be at the begin of set.
    My strategy is simple: the size of set is always equal to k + 1, and test the newly added element and see if that element already exists in set.


Log in to reply
 

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