[剑指offer] 40. 数组中只出现一次的数字

题目描述

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

思路：

解法一:

哈希表

class Solution

{

  public:

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

    {

        map<int, int> mapping;

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

            mapping[data[i]]++;

        vector<int> v;

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

        {

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

                v.push_back(data[i]);

        }

        *num1 = v[];

        *num2 = v[];

    }

};

解法二：

利用异或

1、异或思想，一个数与自己异或为0，一个数与0异或为自己

2、由于其它数字两两相同，所以所有数异或则得到这两个不同数的异或结果。取这个结果的第一个1作为标志位

3、这个标志的1，必须是：这两个数在该位一个为0，一个为1

4、这样可以将数组分为两组，一组在该标志位为1，一组在该标志位为0，这两个不同数字分别在这两组内

5、将两组内的数分别异或，得到两个结果则为这两个不同的数

class Solution

{

  public:

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

    {

        int tempbit = ;

        for (auto c : data)

            tempbit ^= c;

        int sign = ; //记录两个数不同的那一位

        for (; sign < data.size(); sign++)

        {

            if ((tempbit & ( << sign)) != )

                break;

        }

        *num1 = ;

        *num2 = ;

        for (auto c : data)

        {

            if ((c & ( << sign)) == )

                *num1 ^= c;

            else

                *num2 ^= c;

        }

    }

};

巴特西

[剑指offer] 40. 数组中只出现一次的数字

题目描述

最新文章

热门文章