关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2

题目

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)。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-09-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏华章科技

值得收藏的Python小技巧:这17个骚操作你都OK吗?

导读:Python 是一门非常优美的语言,其简洁易用令人不得不感概人生苦短。在本文中,作者 Gautham Santhosh 带我们回顾了 17 个非常有用的 ...

30930
来自专栏小樱的经验随笔

【Java学习笔记之二十二】解析接口在Java继承中的用法及实例分析

一、定义 Java接口(Interface),是一系列方法的声明,是一些方法特征的集合,一个接口只有方法的特征没有方法的实现,因此这些方法可以在不同的地方被不...

33050
来自专栏编程

C语言最难啃的三块硬骨头,你越过去了吗?

提到C语言很多初学者都觉得,学到中间就进行不下去了,因为碰到了几个硬骨头死活翻不过去,于是很多人给C语言下结论太难了,太靠近底层了,特别是那几块难啃的骨头,直接...

24480
来自专栏微信公众号:Java团长

谈谈我对面向对象以及类与对象的理解

对于刚接触JAVA或者其他面向对象编程语言的朋友们来说,可能一开始都很难理解面向对象的概念以及类和对象的关系。笔者曾经带过一个短期培训班教授java入门基础,在...

11420
来自专栏程序员互动联盟

C语言最难啃的三块硬骨头

提到C语言很多初学者都觉得,学到中间就进行不下去了,因为碰到了几个硬骨头死活翻不过去,于是很多人给C语言下结论太难了,太靠近底层了,特别是那几块难啃的骨头,直接...

43550
来自专栏专知

【Leetcode237】关关的刷题日记 71–Leetcode237.Delete Node in a Linked List

关关的刷题日记71 – Leetcode 237. Delete Node in a Linked List 题目 Write a function to de...

27070
来自专栏后端技术探索

常见算法面试题

这几天在网上看到一篇关于算法面试题的博客,归纳的很好,有不少经典的题目,大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考...

32320
来自专栏苦逼的码农

【面试现场】如何实现可以获取最小值的栈?

该公号有个「面试现场」的专题,感觉写的很不错,看了挺有收获,特地转载一篇过来给大伙,希望你们也能有所收获。如果喜欢的话,可以关注该公号呢----「互联网侦察」。...

20520
来自专栏landv

c语言-猜数字游戏

32540
来自专栏iKcamp

翻译连载 |《你不知道的JS》姊妹篇 |《JavaScript 轻量级函数式编程》- 第 6 章:值的不可变性

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 第 6 章:值的不可变性 在第 ...

21550

扫码关注云+社区

领取腾讯云代金券