剑指offer：数组中只出现一次的数字-白红宇

剑指offer：数组中只出现一次的数字

阅读量：5951 次

发布时间：2019-06-19

本文共 1546 字，大约阅读时间需要 5 分钟。

题目描述：

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

思路分析：

1. 直接想法，每个数字遍历，统计出现次数，复杂度O(n^2)，超时。

2. 借助哈希表，空间换时间，遍历一次，时间复杂度O(n)，空间复杂度O(n)，对于空间复杂度限制为O(1)时，不满足条件。

3. 利用异或运算。已知两个相同的数，异或为0。若当前的题目是只求一个只出现一次的数字时，只需要将数组中的数字都异或一次，最后得到的即为所求的只出现一次的数字。那么拓展到两个数字的情况，

我们可以将原始数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现。这样，我们就可以用上述方法找到那个孤苦伶仃的元素。

我们还是从头到尾一次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数组的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于两个数字肯定不一样，那么异或的结果肯定不为0，也就是说这个结果数组的二进制表示至少有一个位为1。我们在结果数组中找到第一个为1的位的位置，记为第n位。现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。

举例：{2,4,3,6,3,2,5,5}

我们依次对数组中的每个数字做异或运行之后，得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个子数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别两个子数组求异或，就能找到第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是4。

代码：

思路二：

1 class Solution { 2 public: 3     void FindNumsAppearOnce(vector
     
       data,int* num1,int *num2) { 4         if(data.size()<=0) 5             return; 6         map
      
        data_map; 7         for(int i=0; i

v;12 for(int i=0; i

思路三：

class Solution {public:    void FindNumsAppearOnce(vector
     
       data,int* num1,int *num2) {        int length = data.size();        if(length<2)            return;        //对原始数组求异或        int resultExclusiveOR = 0;        for(int i=0; i
      
       > 1;            indexBit++;        }        return indexBit;    }    //判断第indexBit位是否为1    bool IsBit1(int num, unsigned int indexBit)    {        num = num >> indexBit;        return (num & 1);    }};

转载于:https://www.cnblogs.com/LJ-LJ/p/10960291.html

你可能感兴趣的文章