Given 2*n + 1 numbers, every numbers occurs twice except one, find it.
Given [1,2,2,1,3,4,3], return 4
刷题中，遇到一个比较有趣的题目，记录一下。
题目给了2*n+1个数，其中有n组数成双出现，只有一只单身贵族。那么如何找到这个数呢？一开始想了一个比较笨的方法，先将数组排序，看连续出现的两个数是否一样，不一样的就是要找的那个。
方法一：
我要评论public class Solution {
/**
* @param A: An integer array
* @return: An integer
*/
public int singleNumber(int[] A) {
// write your code here
Arrays.sort(A);
if(A.length==1){
return A[0];
}
for(int i=0;i<A.length;i+=2){ //注意i迭代数为2
if(i==A.length-1)
return A[i]; //如果是最后一个，直接返回该值
if(A[i]!=A[i+1])
return A[i];
}
return 0;
}
}
方法二：
在网上找到的一种更巧妙的方法，利用“异或”运算的一个性质：（1）一个数与另外两个相同的数异或之后，还等于这个数（2）异或运算的可交换性
例如： 2 XOR 1=3 3 XOR 1=2 也可以描述为 2 XOR (1 XOR 1)=2 XOR 0=2.
对于本题来说，把所有数XOR得到的结果就是那只“单身贵族”：
public class Solution {
/**
* @param A: An integer array
* @return: An integer
*/
public int singleNumber(int[] A) {
//根据题目的意思，A数组中至少有一个数
int res=A[0];
for(int i=1;i<A.length;i++){
res^=A[i];
}
return res;
}
}
如对本文有疑问， 点击进行留言回复！！
现在微服务这么火，你还不了解吗？阿里P8推荐的微服务学习指南
论文笔记：SlowFast Networks for Video Recognition
网友评论