自己的做法
算法思想
使用哈希表，遍历数组，先查看哈希表是否有相同元素，如果有，则停止遍历，返回true；直到遍历结束，返回false。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> numbers;
for(int i = 0; i < nums.size(); i++) {
if(numbers.count(nums[i]) == 0) {
numbers.insert(nums[i]);
} else {
return true;
}
}
return false;
}
};
|
性能分析
时间复杂度：遍历数组，O(n)。
空间复杂度：使用了哈希表，O(n)。
官方做法
算法思想
把数组排序，然后依次比较相邻元素。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() - 1; i++) {
if(nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
};
|
性能分析
时间复杂度：就是排序时间复杂度：O(n∗logn)。
空间复杂度：自己实现排序算法，空间复杂度为O(1)，使用默认排序算法，为O(n)。