# 【LeetCode】Single Number

Single Number
Total Accepted: 19208 Total Submissions: 42682 My Submissions
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 AC 352ms

```public class Solution {
public int singleNumber(int[] A) {
if(A == null || A.length == 0 ){
return 0;
}
int result = A[0];
for(int i = 1; i < A.length; i++){
result ^= A[i];
}
return result;
}
}```

update 2014-06-10(增加python)
Python AC 284ms

```class Solution:
# @param A, a list of integer
# @return an integer
def singleNumber(self, A):
alen = len(A)
result = A[0]
for i in range(1, alen, 1):
result ^= A[i]
return result```

Java AC

```import java.io.StreamTokenizer;

public class Main {
/*
* 1256
*/
public static void main(String[] args) throws Exception {
StreamTokenizer st = new StreamTokenizer(System.in);
while (st.nextToken() != StreamTokenizer.TT_EOF) {
int N = (int) st.nval;
int[] array = new int[N];
int result = 0;
for (int i = 0; i < N; i++) {
st.nextToken();
array[i] = (int) st.nval;
result ^= array[i];
}

int num = 0;
while ((result & 1) == 0) {
result = result >> 1;
num++;
}
int num1 = 0;
int num2 = 0;
for (int i = 0; i < N; i++) {
if (((array[i] >> num) & 1) == 0) {
num1 ^= array[i];
} else {
num2 ^= array[i];
}
}
if (num1 > num2) {
System.out.println(num2 + " " + num1);
} else {
System.out.println(num1 + " " + num2);
}
}
}
}
/**************************************************************
Problem: 1256
User: wangzhenqing
Language: Java
Result: Accepted
Time:770 ms
Memory:33104 kb
****************************************************************/```

LeetCode算是除九度之外的另一个开始吧。加油。