前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-217-Contains Duplicate(使用排序来判断整个数组有没有重复元素)

leetcode-217-Contains Duplicate(使用排序来判断整个数组有没有重复元素)

作者头像
chenjx85
发布2019-03-14 17:15:38
6780
发布2019-03-14 17:15:38
举报
文章被收录于专栏:chenjx85的技术专栏

题目描述:

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.

Example 1:

代码语言:javascript
复制
Input: [1,2,3,1]
Output: true

Example 2:

代码语言:javascript
复制
Input: [1,2,3,4]
Output: false

Example 3:

代码语言:javascript
复制
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

要完成的函数:

bool containsDuplicate(vector<int>& nums) 

说明:

1、给定一个vector,要求判断vector中包不包含重复元素。如果重复,那么返回true,如果全都是不重复的,那么返回false。

2、这道题我们可以用最笨的双重循环来做,也可以增加空间复杂度,建立set,用哈希的方法来判断有没有重复。

笔者也想过能不能用异或来做,最后觉得应该还是不太行。

最终选择了排序的方法,先快排整个vector,接着遍历一次整个vector,判断相邻元素有没有相同的,如果有就返回true,如果跑完一整个循环都没有,那么返回false。

代码十分简单,如下:

代码语言:javascript
复制
    bool containsDuplicate(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());//排序整个vector
        int s1=nums.size();
        for(int i=0;i<s1-1;i++)//从第一个元素开始,到倒数第二个元素结束
        {
            if(nums[i+1]==nums[i])//如果有相同元素
                return true;
        }
        return false;//如果跑完全程都没有相同的
    }

上述代码实测29ms,beats 99.14% of cpp submissions。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-05-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 要完成的函数:
  • 说明:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档