My THREE solutions of this question(C++) with comments


  • 5
    I

    Solution 1:

    sort the vector then
    traverse to find whether there are same value element continuesly

      class Solution {
        public:
        	bool containsDuplicate(vector<int>& nums) {
    	sort(nums.begin(), nums.end());
    	if (nums.size() == 0){
    		return false;
    	}
    	vector<int>::iterator it = nums.begin();
    	int temp = *it;
    	it++;
    	for (; it != nums.end(); it++){
    		if (*it == temp){
    			return true;
    		}
    		temp = *it;
    	}
    
    	return false;
     }
    

    };

    Solution 2:
    step 1 Sort the vector
    step2 use erase to remove the duplicate and compare the size of the vector

    class Solution {
    public:
    	bool containsDuplicate(vector<int>& nums) {
    		int pre = nums.size();
    
    		sort(nums.begin(), nums.end());
    		nums.erase(unique(nums.begin(), nums.end()), nums.end());
    
    		int post = nums.size();
    
    		return (post == pre) ? false : true;
    		return false;
    	}
    };
    

    Solution 3:
    use hash map

    class Solution {
    public:
    	bool containsDuplicate(vector<int>& nums) {
    		unordered_map<int, int> hash;
    		vector<int>::iterator it = nums.begin();
    
    		for (; it != nums.end(); it++){
    			if (hash.find(*it) != hash.end()){
    				return true;
    			}
    			hash[*it] = 1;
    		}
    
    		return false;
    };

  • 0
    J

    Solution 3 has you using a hash map to approximate what the set data type does for you already, store only unique elements. So should be able to check and see if an item already exists (quickly) without worrying about the values of keys.


  • 0
    J

    Excuse me,could you tell me why the second method is faster? : )


Log in to reply
 

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