记一个精巧的算法与一段感伤的话

发表于 | 分类于 | 评论数： | 阅读次数：

  5月20号，中午吃饭，看见一道很有意思的题，题面很简单：

  给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

这道题解法颇多，但如果要求时间复杂度为O(n)，空间复杂度为O(1)，问题就似乎变得有挑战性了。

  此题的正解非常简单也极其巧妙：将所有元素做异或运算，即a[1] ⊕ a[2] ⊕ a[3] ⊕ … ⊕ a[n]，所得的结果就是那个只出现一次的数字。
  原理很好理解：出现2次（可推广为偶数次）的元素经过按位异或后全部变为0，而出现1次（可推广为奇数次）的元素与0进行异或后会被保留。因此所有元素依次异或后得到的结果即为所求。
代码如下：

1
2
3
4
5
6
7
8
// LeetCode No.136
int singleNumber(int *nums, int numsSize)
{
    int ans = 0;
    for(int i = 0; i < numsSize; ++i)
        ans ^= nums[i];
    return ans;
}

  晚上打完球回到宿舍，看到下面这段话，有所触动，一种难以言状的思绪在心中徘徊。在此把这段话摘录下来：

年轻时
你做了一个决定
要把生命献给爱情

后来
万箭穿心的时候
你没事
因为青春替你抵了命

青春死了
但你还活着
可你却再也不会心动了

每个人都要熬过一段
付出很多却没有结果的爱情
才会一夜之间突然长大

所以不要笑话一个人面无表情
你只是没看到过
他汹涌的内心