LeetCode: 存在重复

[resse92]

用map来保存对应的数字出现的次数。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        map<int, int> mmap;
        for (int i = 0; i < nums.size(); i++) {
            if (mmap.find(nums[i]) != mmap.end()) {
                return true;
            }
            mmap.insert(make_pair(nums[i], 1));
        }
        return false;
    }
};

另外，如果nums的数字取值范围小于nums.size()时，可以直接遍历数组交换相应位置，将时间复杂度下降到O(logn):

bool containsDuplicate(vector<int>& nums) {
	for(int i = 1; i < nums.size(); ++i){
		while(nums[i] != i){
			int idx = nums[i];
			if(nums[i] == nums[idx])
				return true;
			swap(nums[i], nums[idx]);
		}
	}
	return false;
}