C++存在重复元素(三种解法详解)

题目链接：存在重复元素

题目描述

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

样例输入与输出

示例1：
输入：[1,2,3,1]
输出：true
示例2：
输入：[1,2,3,4]
输出：false
示例3：
输入：[1,1,1,3,3,4,3,2,4,2]
输出：true

解法1(排序)

思路

将所有元素排好序，然后扫描数组，如果一个数与它前一个元素相等，那么就是重复的。

代码

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size() == 0 || nums.size() == 1)
            return false;
        sort(nums.begin(),nums.end());
        for(int i = 1;i < nums.size();i++)
            if(nums[i] == nums[i-1])
                return true;
        return false;
    }
};

//此题使用快速排序会超时，这是因为STL中sort()函数不止用到快速排序，具体原理会在下一篇讲述
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size() == 0 || nums.size() == 1)
            return false;
        quicksort(nums,0,nums.size()-1);
        for(int i = 1;i < nums.size();i++)
            if(nums[i] == nums[i-1])
                return true;
        return false;
    }
    void quicksort(vector<int>& a,int s,int e)
    {
        if(s>=e)
            return;
        int k=a[s];
        int i=s,j=e;
        while(i!=j)
        {
            while(j>i&&a[j]>=k)
                --j;
            swap(a[i],a[j]);
            while(i<j&&a[i]<=k)
                ++i;
            swap(a[i],a[j]);
        }
        quicksort(a,s,i-1);
        quicksort(a,i+1,e);
    }
};

复杂度分析

扫描一次复杂度为O(n)，因此算法复杂度取决于排序的复杂度，以快排为例，时间复杂度为O(nlogn)

空间复杂度为 O(logn)

解法2(利用数组值当索引)

思路

从头到尾遍历数组，对于相同的数组元素，利用它们元素值返回的下标必然一样，举个例子

a[1,2,3,4,1]
创建相同大小的判断数组
b[false,false,false,false,false]
b[a[0]] = b[1] = false，b[a[4]] = b[1] = false

接下来需要处理数组中有负数的情况，因为数组的索引不能为负，我的处理办法是找到最小值，然后给每个数组元素加上它的绝对值。

在此基础上，还需要找到最大值，因为是以原数组的元素值作为索引，所以需要创建一个以(处理完负数后)最大值为大小的判断数组。

代码

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size() == 0)
            return false;
        int minvalue = nums[0],maxvalue=nums[0];
        for(int i = 0;i < nums.size();i++)
            minvalue = min(minvalue,nums[i]);
        for(int i = 0;i < nums.size();i++){    //消除所有负数
            if(minvalue < 0)
                nums[i] += abs(minvalue);
            maxvalue = max(maxvalue,nums[i]);
        }
        bool *Judge;
        Judge = (bool *) malloc (sizeof(bool)*(maxvalue+1));
        memset(Judge,false,(maxvalue+1)*sizeof(bool)); //创建最大值+最小值绝对值大小的判断数组
        for(int i = 0;i < nums.size();i++){   //从头扫描，若judge[i]为true，说明已经有相同元素了
            if(Judge[nums[i]] == false)  
                Judge[nums[i]] = true;
            else
                return true;
        }
        return false;
    }
};

复杂度分析

只需要遍历一遍数组，因此时间复杂度为O(n)

需要创建一个以数组元素最大值+最小值绝对值大小的数组，空间复杂度不太容易确定，应该是 >O(n)

解法3(哈希，LeetCode官方解答)

思路

对于数组中每个元素，将其插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。 原理跟解法2相似

代码

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for (int x: nums) {
            if (s.find(x) != s.end()) {
                return true;
            }
            s.insert(x);
        }
        return false;
    }
};

复杂度分析

时间复杂度O(n)

空间复杂度O(n)