LeetCode 1, Single Number I

今天研究第一个LeetCode问题，按照计划AC Rate排序，通过率最高的就属这个了，那么就拿他当做入门第一课吧。

题目 Single Number I

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解题过程

独立分析：

实话实说，这个我自己硬是没有想到好的算法来满足题目的要求，悲哀。排序什么的，直接太弱了

网络提示：

根据Google的搜索结果找到了这里: 靖空间

原文已经分析的很透彻了，解决这道题的主要思路就是用位运算，这玩意平常在代码里看到很多奇淫巧技都用位来操作，比如对个齐啊，算个地址啊等等，但看来自己还是没有掌握，今天就没有想起来，离散数学没学好，对位的操作没有理解到位。

异或的核心思想就是：a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

换做通俗一点的话讲：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。

根据这个道理，那么这道题就可以这样写了

class Solution {
public:
    int singleNumber(int A[], int n) {
    	assert(A != NULL && n > 0);
        int x = 0;
        for(int i = 0; i < n; i++) {
            x = x ^ A[i];
        }
        return x;
        
    }
};

每一次让x去和数组里面的数做一次异或运算，那么当两个数相同的时候，对应的位就会被清空，留在最后的就是那个落单的了。

位运算原来还能这样玩，计算机理论里面的东西看来只有做做算法题才能巩固了。

今天第一天，找个简单的练手，没想到还是摔了，木事，站起来继续