本文最后更新于 372 天前,其中的信息可能已经有所发展或是发生改变。
一、题述
给定一个整数数组,判断是否存在重复元素。
如果存在一值在数组中出现至少两次,函数返回 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
二、题解
1、直接排序法
对给定数组进行排序,再对其进行遍历,若有重复元素,则直接退出循环,返回False。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
};
复杂度分析
- 时间复杂度:
O(NlogN)
,其中 N 为数组的长度。
- 空间复杂度:
O(logN)
,其中 N 为数组的长度。
2、哈希表
- 创建一个哈希表,然后从左往右遍历数组。
- 检测哈希表中是否已存在当前字符,若存在,直接返回结果,若不存在,将当前字符加入哈希表,供后续判断使用即可。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> s;
for (int x: nums) {
if (s.find(x) != s.end()) {
/**
如果x在哈希表中已经存在,则find返回x对应的迭代器,如果x不存在,则find返回unordered_set::end。因此可以通过
map.find(x) == map.end()
来判断,x是否存在于当前的unordered_set中。
**/
return true;
}
s.insert(x);
}
return false;
}
};
复杂度分析
- 时间复杂度:O(N),其中 N 为数组的长度。
- 空间复杂度:O(N),其中 N 为数组的长度。
P.S. 哈希表
拥有记数的功能,如果题目中包含字眼至多xx次
, 至少xx次
,唯一
等等字眼,可以联想到用哈希表来解决