数组中只出现一次的数字（hash法+异或法）——剑指Offer

57 阅读 0 评论 38 点赞

我是靠谱客的博主追寻画笔，最近开发中收集的这篇文章主要介绍数组中只出现一次的数字（hash法+异或法）——剑指Offer，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

题目分析

这个题目主要有两种方法：
1.hash法
2.异或法

hash法是先遍历一遍数组利用map记录数字出现的此时，第二次遍历则将出现次数为1的数存入vecor数组并输出。

时间复杂度：O(n)
空间复杂度：O(n)
异或法的思路是：首先明确异或运算的规则：相同两个数异或为0，不同两个数异或为1，任何数和0异或值都不变。
1.先将数组中的所有数异或一下，出现两次的数异或不改变结果，最终得到的结果result是两个出现次数为1的数。
2.其中result中二进制1一定由0和1（1和0）异或而成，因此只需要将0和出现次数为1的数异或，结果就是出现次数为1的数。
**注意：**计算机中存储的二进制数是补码，因此需要将补码转换为原码：
正数的原码与补码相同。
负数的原码=补码&(-补码)。
时间复杂度：O(n)
空间复杂度：O(1)

代码

C++代码如下：

1.hash法：

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) 
    {
        unordered_map<int,int> map;
        for(const int k : data) ++map[k];
        vector<int> num;
        for(const int k : data)
        {
            if(map[k]==1)
                num.push_back(k);
        }
        *num1=num[0];
        *num2=num[1];
    }
};

2.异或法：

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) 
    {
       int result=0;
        for(const int k : data)
        {
            result^=k;
        }
        result&=(-result);
        *num1=0;
        *num2=0;
        for(const int k : data)
        {
            if(k&result) 
                *num1^=k;
            else
                *num2^=k;
        }
    }
};