关关的刷题日记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)。

欢迎使用专知!点击阅读原文即可访问,获取更多AI知识资源。同时请关注我们的公众号,获取最新关于专知以及人工智能的资讯、技术、算法等内容。

点击右上角,把文章分享到朋友圈

展开全文
Top
微信扫码咨询专知VIP会员