关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2
关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2
WZEARW
发布于 2018-04-08 17:13:11
发布于 2018-04-08 17:13:11
题目
Leetcode 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.
题目的意思是，判断一个数组中是否有重复的数，有的话返回true，否则返回false。
方法1
方法1：对数组进行排序，遍历数组，如果出现前后元素相等，说明有重复数。
时间复杂度o(nlogn)，不需要开辟额外空间。
代码如下：
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;
}
};注意代码的5-7行不要写成下面这种形式，理由是：nums.size()是个unsigned int型，当数组大小为0的时候，nums.size()-1并不会得到-1，而是一个非常大的正数，这个时候数组会越界，会runtime error。
for(int i=0; i<nums.size()-1; i++)
{
if(nums[i]==nums[i+1])优雅的代码：既然用了sort，不如直接用unique：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
return unique(nums.begin(), nums.end())!=nums.end();
}
};方法2
方法2：用哈希表，对数组中的每个元素先去哈希表中查找，如果找到了就直接返回true，找不到的话就把这个元素插入到表中，时间复杂度o(n).
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int>t;
for(int x: nums)
{
if(t.find(x)!=t.end())
return true;
else
t.insert(x);
}
return false;
}
};现在的努力是为了将来更有能力选择自己的人生，加油！
以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2017-09-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录