【《漫画算法》笔记】找数组中出现奇数次的元素

本文主要是介绍【《漫画算法》笔记】找数组中出现奇数次的元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定数组，只有一个元素出现过奇数次

思路：
考虑到异或运算的性质——两个等值数的异或结果等于0，两个不等值的数异或结果为1，
将给定数组的所有元素异或起来，最终结果就是那个“唯一出现过计数次”的数。

给定数组，只有两个元素出现过奇数次

思路：
在上述的基础上，同样对所有元素做异或运算，那么结果必然不是0。也就是说，异或的结果存在某一位非0，假设第a位。这提醒我们，可以根据这个非零位对给定数组中的元素进行分类——分成两类。第一类，二进制表示第a位上为0的元素；第二类，二进制表示第a位上为1的元素。

import java.util.Arrays;public class findLostNum {public static int[] find2Num(int[] arr){int[] res=new int[2];int xor=0;for (int i = 0; i < arr.length; i++) {xor^=arr[i];}if(xor==0){return null;}int sep=1;while ((xor&sep)==0){ // 找到xor的二进制表示 最靠右 的‘1’ 的位置sep<<=1;}for (int i = 0; i < arr.length; i++) {if((sep&arr[i])==0){res[0]^=arr[i];}else {res[1]^=arr[i];}}return res;}public static void main(String[] args) {int[] array=new int[]{4,1,2,2,5,1,4,3};int[] res=find2Num(array);System.out.println(Arrays.toString(res));}
}

这篇关于【《漫画算法》笔记】找数组中出现奇数次的元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---