LN : leetcode 217 Contains Duplicate
2024-08-30 20:20:20
lc 217 Contains Duplicate
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
方法一 Time Limit Exceeded##
首先想到的就是比较暴力,没有技巧性可言的时间复杂度为O(\(n^{2}\))的方法。显而易见,这个方法非常没有效率,通不过测试, Time Limit Exceeded。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if (nums.empty()) return false;
for (int i = 0; i < nums.size(); i++) {
for (int j = i+1; j < nums.size(); j++) {
if (nums[i] == nums[j]) return true;
}
}
return false;
}
};
方法二 Time Limit Exceeded##
运用迭代器iterator的find()函数来查找是否有重复的整数。虽然看上去只有一层循环,但是find()本身就相当于一次循环,所以算法的时间复杂度并没有提高,依旧是O(\(n^{2}\))
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
for (int i = nums.size()-1; i > 0; i--) {
int temp = nums[i];
nums[i] = NULL;
vector<int>::iterator result = find( nums.begin( ), nums.end( ), temp);
if (result != nums.end()) return true;
nums[i] = temp;
}
return false;
}
};
方法三 Accepted##
利用STL中set中元素都是唯一的这一特点,可以用来去重。以此对比vector和set中的数据个数,可以说是很巧妙的方法了。
#include <set>
using namespace std;
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
return nums.size() > set<int>(nums.begin(), nums.end()).size();
}
};
最新文章
- Fedora 22中的DNF软件包管理工具
- TypeError: datetime.datetime(2016, 9, 25, 21, 12, 19, 135649) is not JSON serializable解决办法
- 实现winform DataGridView控件判断滚动条是否滚动到当前已加载的数据行底部
- CodeCover初体验
- 下拉刷新列表添加SwipeDismissListViewTouchListener实现滑动删除某一列。
- 45. Jump Game II
- iOS多线程常用类说明--备用参考
- css3图片滤镜
- NOIP2014D2T2寻找道路
- Bootstrap进度条
- win10环境下tensorflow-gpu安装
- nginx 项目部署
- extremecomponents
- 删除a表中和b表相同的数据
- 网页Title加LOGO图标
- POJ2236
- 【Android】Android输入子系统
- Sorl搜索技术
- 再谈fedora 23中的flash的安装
- selenuim和phantonJs处理网页动态加载数据的爬取