-12-13 存在重复元素

问题

2020-12-13 存在重复元素


解决方法

法一：排序

先对数组排序，然后从前之后逐一检查即可。

class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == nums[i-1]) {
return true;
}
}
return false;
}
};

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(1)\)

提交结果：
2020-12-13 存在重复元素

法二：哈希表

从前至后遍历数组元素，检查其是否已在哈希表中，若存在，直接返回true;若不存在，则将当前元素添加入哈希表中。

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

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

提交结果：
2020-12-13 存在重复元素

使用\(set\)的提交结果：
2020-12-13 存在重复元素


总结

在使用STL的时候，我一开始使用的是\(set\)，但是发现使用\(set\)耗时特别多，在看了题解至后才知道应该使用\(unordered_set\)。

因为\(set\)使用红黑树实现，而\(unorderd_set\)才使用哈希表实现。

参考：set与unorderd_set的区别,set,unordered_set。
使用set的情况：

  • 需要有序数据

  • 按顺序访问

  • 需要元素的前身/后继

使用unordered_set:

  • 需要保存一组无序的元素

  • 需要单个元素访问，即没有遍历

以上是 -12-13 存在重复元素 的全部内容， 来源链接： utcz.com/a/76633.html

回到顶部