LeetCode 217. 存在重复元素
原题链接
简单
作者:
bruce
,
2021-01-26 14:21:51
,
所有人可见
,
阅读 257
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
/**
* 217 给定一个无序的整数数组,然后求出这个整数数组的重复元素即可
*
* Example 1:
* Input: [1,2,3,1]
* Output: true
*
* Example 2:
* Input: [1,2,3,4]
* Output: false
*
* 判断是否数组中出现重复的数
*/
/**
* 方法 1, 利用hash_map来做,把数组的出现次数放进hashmap中,每次查看,如果出现了这个数字,直接返回true;
* 时间复杂度是O(n),空间复杂度是O(n)
*/
bool containsDuplicate1(vector<int> &nums)
{
unordered_map<int, int> res;
for (int i = 0; i < nums.size(); i++)
{
if (res.find(nums[i]) != res.end()) // hashmap的find函数
return true;
++res[nums[i]];
}
return false;
}
/**
* 方法 2,和上面类似的思路,就是用其他容器来实现
*/
bool containsDuplicate2(vector<int> &nums)
{
unordered_set<int> s;
for (int i = 0; i < nums.size(); i++)
{
if (s.count(nums[i]))
return true;
else
s.insert(nums[i]);
}
return false;
}