Single Number

Single Number

---

今天是一道有关位运算的题目，来自LeetCode(#136)，难度为Medium，Acceptance为46.5%。

这类题目不需要太多的算法知识，需要的知识位运算的基础知识和经验。

题目如下

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 ?

解题思路及代码见阅读原文

思路如下

其实，该题的思路较为简单，只要想到使用位运算就很容易想到。题目中除一个数之外，其他数字都出现两次，可以想到两个相同的数做异或得到了，这样将所有的数做异或就可以得到那个只出现一次的数。

代码如下

java版

public class Solution {
    /**
     *@param A : an integer array
     *return : a integer 
     */
    public int singleNumber(int[] A) {
        int ans = 0;
        for(int i : A)
            ans ^= i;
        return ans;
    }
}

c++版

int singleNumber(int A[], int n) {
    int result = 0;
    for (int i = 0; i<n; i++) {
        result ^=A[i];
    }
    return result;
}