LeetCode217 & 136

存在重复元素 1. 题目描述

给你一个整数数组nums，如果任一值在数组中出现至少两次，返回true；如果数组中元素互不相同，返回false。

示例
输入：nums=[1,2,3,1]
输出：true

2. 解法 2.1 排序

利用sort函数将数组排序，那么重复元素一定相邻，基于此编写程序。

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

2.2 哈希

容器set中只会保留不重复的元素，将nums中元素插入set中，如果每个数都插入成功，则不包含重复元素，返回false，否则返回true。

set.insert()函数的返回值为pair(iterator,bool)，第一个参数表示插入数据的迭代器，第二个表示是否插入成功，因此可以用第二个参数表示插入成功与否。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) 
    {
        unordered_set<int> s;
        for(auto r : nums)
        {
            auto res = s.insert(r).second;
            if(!res)//如果插入不成功，表明有重复元素
            {
                return true;
            }
        }//循环走完，未发现重复元素
        return false;
    }
};

只出现一次的数字

这一题遇上一题有相似的解法，因此放到一起。

1. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次外，其余每个元素均出现两次。找出那个只出现一次的元素。

说明：
你的算法应该具有线性时间复杂度。或者 O ( 1 ) O(1) O(1)的空间复杂度。

示例
输入：[2,2,1]
输出：1

2. 解法 2.1 哈希

看到重复数字，想到哈希。上一题是利用哈希表能否插入判断是否有重复元素，这一题同样利用这一点，但是思路得多一层，不仅得知道插入是否成功，还得把第二次不成功但是第一次成功的元素删除。

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        unordered_set<int> s;
        for(int r : nums)
        {
            if(!s.insert(r).second)//如果r插入不成功
            {
                s.erase(r);//那么删除之前插入的r
            }
        }
        return *s.begin();//最后只会剩下一个元素，就是我们需要的只出现一次的元素
    }
};

2.2 位运算

异或运算规则为：相同为0，相异为1。对于int类型的数据a，b，c，有如下的运算规则:

0^a = a
a^a = 0
a^ b ^ c = a ^ c ^ b
用vs测试，cout << a^b输出结果为 a+b的值

根据以上规则，倘若我们把nums中的所有元素异或，那么相同的值异或为0，最后只剩下只出现一次的元素。

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ans = 0;
        for(int i = 0; i != nums.size(); ++i)
        {
            ans ^= nums.at(i);
        }
        return ans;
    }
};