找出数组中只出现一次的数字
一个数组中，有一个数字只出现一次，其余的数都出现两次，求出那个单独的数
可以使用异或或来解决这个问题，因为两个相同的数异或之后就是0，0与一个数异或还是这个数，而且异或满足交换律
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 1};
int n=0;
for (int i = 0; i < arr.length; i++) {
n ^= arr[i];//与sun+=arr[i]类似，方便理解
}
System.out.println(n);
}拓展：
一个数组中，只有两个不同的数字出现一次，其余的数都出现两次，求出那两个只出现一次的数
思路：假设数组是{1,2,3,1}，要想找到那两个只出现一次的数，只需要将数组里面所有的数字异或一下，得到结果sum，然后将sum进行移位操作判断是否为1，如果不为1，依次往后，知道右移到位为1的时候为止，其实就是确定sum从右往左数第几位是1，从而起到筛选的作用，
接下来将数组遍历一遍，判断数组中的每个数是否满足移k位结果是否为1，(((sum >> k) & 1)是常见的判断位数上是1还是0的方法)，如果是1，就将其全部异或起来，这样就可以找到num1
当找到num1时，num2=sum^num1,因为sum=num1 ^num2,所以在异或一个num1就可以得到num2
总结：简单来说，就是通过移位操作来达到分类的作用，接下来就是使用之前异或的方法即可
代码如下
public static int[] Search(int[] arr) {
int sum = 0;
int num1 = 0;
int num2 = 0;
int k = 0;
for (int i = 0; i < arr.length; i++) {
sum ^= arr[i];
}
while (((sum >> k) & 1) != 1) {
k++;
}
for (int i = 0; i < arr.length; i++) {
if ((arr[i] >> k & 1) == 1) {
num1 ^= arr[i];
}
}
num2 = sum ^ num1;
return new int[]{num1, num2};
}
public static void main(String[] args) {
int[] arr = {6, 3, 2, 4, 3, 6};
System.out.println(Arrays.toString(Search(arr)));
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读