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

题目

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：对数组进行排序，遍历数组，如果出现前后元素相等，说明有重复数。 时间复杂度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：用哈希表，对数组中的每个元素先去哈希表中查找，如果找到了就直接返回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）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。