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

题目描述：

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

思路分析：

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。

代码：

思路二：

 class Solution {

 public:

     void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {

         if(data.size()<=)

             return;

         map<int, int> data_map;

         for(int i=; i<data.size(); i++)

         {

             data_map[data[i]]++;

         }

         vector<int> v;

         for(int i=; i<data.size(); i++)

         {

             if(data_map[data[i]]==)

                 v.push_back(data[i]);

         }

         *num1 = v[];

         *num2 = v[];

     }

 };

思路三：

class Solution {

public:

    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {

        int length = data.size();

        if(length<)

            return;

        //对原始数组求异或

        int resultExclusiveOR = ;

        for(int i=; i<length; i++)

            resultExclusiveOR ^= data[i];

        unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);

        *num1 = ;

        *num2 = ;

        for(int j=; j<length; j++)

        {

            if(IsBit1(data[j], indexOf1))

            {

                *num1 ^= data[j];

            }

            else

            {

                *num2 ^= data[j];

            }

        }

    }

private:

    //找到二进制数num第一个为1的位数，如0010，第一个为1的位数是2

    unsigned int FindFirstBitIs1(int num)

    {

        unsigned int indexBit = ;

        //只判断一个字节的

        while((num & )== && (indexBit < *sizeof(unsigned int)))

        {

            num = num >> ;

            indexBit++;

        }

        return indexBit;

    }

    //判断第indexBit位是否为1

    bool IsBit1(int num, unsigned int indexBit)

    {

        num = num >> indexBit;

        return (num & );

    }

};

巴特西

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

最新文章

热门文章