今日力扣每日一题（只出现一次的数字）

　　今天力扣的每日一题是一道看起来非常简单的题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。但是要求时间复杂度是线性的，就是要求O(n) = n?个人思路是逐个比较，如果相同则剔除该两个元素，继续从第0个元素重新比较，如果比较到最后也没有相同的元素，则输出该数。（感觉这样做时间复杂度还是O(n) = n²）

　　不过想了很久还是不知道如何实现。但为了完成这每日一题，我注意到了题目说除了要求的元素外每个元素均出现两次，如果我把这数组按照从小到大排列，然后两两比较，不相同的话则可以求得单独的那个数了。但是对于数组的排列，时间复杂度肯定是n²了。只怪自己才疏学浅，还是先把题目解出来再看看力扣网友的精彩解题思路吧。以下是我写的实现代码：

int singleNumber(int* nums, int numsSize)
{
    int i = 0, j = 0,t;
/*冒泡排序*/
    for(i; i<numsSize; i++)
        for(j = i+1; j<numsSize; j++)
        {
            if(nums[i]>nums[j])
            {
                t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
/*查找该single元素，步进2*/
     for(i = 0; i<numsSize; i+=2)
            {
                if(i == numsSize-1) break;   //如果到最后一个元素，再比较nums[i+1]就会越界了，所以直接break跳出
                else if(nums[i] == nums[i+1]) continue;//如果两数相同，则继续下两个数的比较
                else break;//如果两数不同，则跳出循环
            }
        
    return nums[i];
    
    
}

　　该算法的时间复杂度不堪入目??，还不符合题目的线性的要求，百分制个人给10分吧。

/*********************************************************************************************************************/

　　刚刚去看了看题解，觉得我就是个废物(⊙﹏⊙)。题解是用位运算异或来计算。异或具有以下三个特点：

①任何数和0做异或运算，结果仍然是原来的数；

②任何数和自身做异或运算，结果是0；

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

　　又因为题中限制了相同的元素只会出现两次，所以每两个相同的元素异或结果就是0，全部元素做异或运算，最后的结果就是要求的那个single的数。代码如下：

int singleNumber(int* nums, int numsSize)
{
    int i = 0;
    int result = 0;
    for(i; i<numsSize; i++)
    {
        result ^= nums[i];
    }
    return result;
}

　　虽然看书时有提到过&、|、^等运算，但我从来都是不深入去研究其工作原理和规律，在解决问题的时候就少了很多思路。。其实位运算是对二进制数进行操作的运算，熟练掌握这些运算对于程序的改进会有很大的提升。

今日力扣每日一题（只出现一次的数字）

原文：https://www.cnblogs.com/teamcolt/p/12891179.html