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?
我的代码：
public class Solution {
public static int singleNumber(int[] A) {
int count = A.length;
int[] B = new int[count];
int k=0,single=A[0];
for(int i=1;i<count;i++){
if(A[i]!=single){
continue;
}else{
B[i]=1;
k=findNextEqualsZero(B,k+1);
i=k;
single = A[k];
}
}
return single;
}
public static int findNextEqualsZero(int []B,int locate){
while(B[locate]==1){
locate++;
}
return locate;
}
}
我的想法是，先让single等于最开始的数，然后从头开始找，依次和后面的数对比，如果找到相同的数字，就将single向后挪一位，直到找到i==count的时候，single的值就是要得到的数字。
之后看了其他人的代码，时间复杂度最小的是O(n),使用异或运算，将所有的数字异或，最后的结果就是single数字，或者将所有数字sort一下，然后就可以依次判断两两之间是否相等，时间复杂度未O(nlogn)