qiaoxu123
11/8/2018 - 11:36 PM

217. Contains Duplicate

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1] 输出: true 示例 2:

输入: [1,2,3,4] 输出: false 示例 3:

输入: [1,1,1,3,3,4,3,2,4,2] 输出: true

test1.cpp
content_copyfile_download
//思路：使用C++中STL，find()函数
//时间：1676 ms

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size() <= 1) return false;
        for(vector<int>::iterator it = nums.begin();it != nums.end();++it)
            if(find(it + 1,nums.end(),*it) != nums.end())
                return true;
        return false;
    }
};
test2.cpp
content_copyfile_download
//思路：先对数组进行排序，然后比较相邻两个数即可
//时间：24 ms
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size() <= 1) return false;
        sort(nums.begin(),nums.end());
        
        for(int i = 0;i < nums.size();++i)
            if(nums[i] == nums[i+1])
                return true;
        return false;
    }
};
test3.cpp
content_copyfile_download
// 依旧是使用STL中的hash表来实现，只不过是使用count来解决
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> array;
        
        for (auto i : nums) {
            if(array.count(i)) return true;
            else array.insert(i);
        }
        
        return false;
    }
};