第九周：136. Single Number

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?

Subscribe to see which companies asked this question.

一开始我在想直接进行两次遍历就可以找到这么数，可是这样的话所需的时间复杂度为O(N^2)，这也直接导致超时，于是上网找了一个方法，利用异或的性质：两个相同的数进行按位异或运算结果一定为0，一个数与0按位异或结果即为该数本身。这样一次遍历时间复杂度就是O(N)，不过我想到如果一个数组是无序的，那可不可以做到时间复杂度为O(N)，到现在我还没做出来==。先放上Accepted Code：

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