题目的主要信息:

  • 一个整数数组,除了一个元素只出现了一次,其他元素都出现了两次
  • 需要找出这个只出现一次的数组

方法一:哈希表

具体做法:

我们可以使用哈希表记录数组元素出现的次数,利用其快速访问特点快速去重。哈希表key值记录遇到的数组元素,第一次遇到次数计为1,后续如果再在哈希表中找到这个数字说明第二次遇到,则可以去除哈希表这个key值。

遍历结束后,如果哈希表不为空,说明找到了这个出现次数为1的数字,因为出现次数为2的都被去掉了,哈希表唯一一个元素就是。

alt

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int, int> mp;  //哈希表去重
        for(int i = 0; i < nums.size(); i++){ //遍历数组
            if(mp.find(nums[i]) != mp.end()) //遇到重复的就去除
                mp.erase(nums[i]);
            else //遇到非重复的就记录次数为1
                mp[nums[i]] = 1;
        }
        if(!mp.empty()){ //最后如果哈希表不为空,就剩下只出现一次的数字
            auto iter = mp.begin();
            return iter->first;
        }
        return 0;
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),遍历一次数组,每次哈希表操作都是O(1)O(1)
  • 空间复杂度:O(n)O(n),哈希表最大空间为不同数组元素的个数,最多有(n1)/2+1(n-1)/2+1

方法二:位运算

具体做法:

性质1:0与任何整数异或运算后结果还是该整数

性质2:两个相同的数异或运算后结果为0

性质3:异或运算具有交换律

利用上述三个性质,可以遍历数组,对每个数组元素累异或运算,最后所有出现两次的整数都会被相互消掉为0,而0与出现一次的数异或还是该数字,因此最后的结果就是要求的出现次数为1次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0; //0异或任何数得原数
        for(int i = 0; i < nums.size(); i++) 
            res ^= nums[i]; //累异或运算消去重复元素
        return res;
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),遍历一次数组
  • 空间复杂度:O(1)O(1),没有使用额外的辅助空间