LeetCode题解:只出现过一次的数字

题目描述:

        在一个非空vector容器中存在一些数字,其中只有一个数字只出现过一次其余数字都出现了两次。编写一个函数找到这个只出现过一次的数字。

要求:

        不使用额外空间,并且算法应呈线性的时间复杂度。

解题核心:

        按位异或运算,其中C++中按位异或运算符为^ 。

解题思路:

        两数的按位异或运算即将两数转换为二进制表示后按低位对齐,高位补0,逐位比较,当某一个数的当前位为1而另一数的当前位为0时得到的当前位为1,否则为0

        此处数字1为50(二进制表示为110010)。

        数字2为23(二进制表示为10111)。

        将其分别转换为二进制表示后低位对齐,高位补0。

        逐位比对,得到运算结果37(二进制表示为100101)。

LeetCode题解:只出现过一次的数字_第1张图片

         至此,我们了解了异或运算的规则,我们可以根据百度到的一些异或运算的性质来完成本题。

        性质一:

                 任何数与0做异或运算结果都为其本身。

        性质二:

                自反性,任何数与自身做异或运算结果都为0。

        性质三:

                 异或运算满足结合律与交换律。

        以上两个性质都可以有异或运算的规则轻易得到,在此不作过多说明。

        故本题思路:用0依次与容器中的数做异或运算,由于以上性质,0每次与出现过两次的数做异或运算最终结果会变为0,而0与只出现过一次的数做异或运算会变为该数,故最后得到的运算结果即为只出现过一次的数。

代码实现:

        C++:

int singleNumber(vector& nums) 
{
    int ans = 0;
    for(int i = 0 ; i < nums.size() ; i ++)
    {
        ans ^= nums[i];
    }
    return ans;
}

本题出处: 

        136. 只出现一次的数字

 

 

你可能感兴趣的