算法形容

在左程云左神的算法课上，有这样一道例题：已知数组int[] arr :Q1：在arr中，只有一种数呈现了奇数次，其余数均呈现偶数次，请找出这个呈现了奇数次的数。Q2：在arr中，有两种数呈现了奇数次，其余数均呈现偶数次，请找出这两个呈现了奇数次的数。例：int[] {2,2,3,3,4,4,5,5,5},5呈现了3次，奇数次。其余数字均呈现两次，偶数次。

异或运算的性质

异或运算：按位运算，如果a、b两个值不雷同，则异或后果为1。如果a、b两个值雷同，异或后果为0。符号xor，记作^。例：a=00101011b,b=10110100b,a^b=10010001b**性质：**1.归零率：a^a=0;2.恒等率：a^0=a;3.交换律：a^b=b^a;4.结合律：a^b^c=(a^b)^c=a^(b^c);5.自反：a^b^a=b;

Q1:一种数呈现了奇数次

利用异或运算的性质1归零率，偶数次呈现的数顺次纳闷，后果为0。奇数次呈现的数顺次异或，后果为数自身。再依据性质2恒等率，一个数异或0则等于其自身。 这样将数组里所有的数顺次异或，失去的后果则是呈现了基数次的那个数。
public static void PointOddTimesNumQ1Func(int[] arr){        int eor = 0;        for (int cur : arr) {            eor^=cur;        }         System.out.println(“呈现基数次的数为：”+eor);    }

Q2两种书呈现了奇数次

假如a呈现了奇数次，b呈现了奇数次，首先表明a≠b，所以a^b不等于0。由此可得，a与b的二进制数，必然存在某一位不雷同。第一步：咱们首先，将数组内的所有元素顺次异或，依据异或运算的性质，得int[] arr顺次异或的后果=a^b;咱们记作eor=a^b;第二步，找到a与b的二进制数不雷同的最低位例：a = 10001000b，b=0110000b，a与b的第三位不同，则这一位的异或后果为1，咱们去尝试找到这一位。eor=a^b=11101000，则最低位=eor&(~eor+1)=00001000b，咱们记作rightBit，咱们可失去，a与b的二进制的第3位必定是不雷同的。第三步：遍历整个数组，每一个数字与rightBit进行与运算（cur&rightBit），如果失去的后果为0，则示意，有可能这个数为a/b其中的一个，然而如果是a，则示意a的二进制在第3位必定为0，则b的第3位必定为1。这样咱们就能将a和b划分分明界线。或者用cur&rightBit==rightBit判断，这样筛选进去的所有数，都是第3位为1的数，因为a和b是绝对独立的，则非a即b。第四步，将第三步筛选进去的所有数进行顺次异或运算。因为其余数都是偶数次呈现，所以不论筛选进去其余数第三位是什么，他们本身异或的后果都是0。这样就相当于，对a或者b做了一次独立异或。异或的后果则是a或b，这样就找出了a/b。eor=a^b,咱们用a/b其中的一个，去异或eor，则失去另外一个数。

留神：第三四步的核心思想，其实是怎么将a和b这两个呈现了奇数次的数字进行宰割。

public static void PointOddTimesNumQ2Func(int[] arr) {        int eor = 0;        for (int cur : arr) {            eor^=cur;        }        int rightBit =0;        rightBit = eor & (~eor+1);        int eorAnother=0;        for (int cur : arr) {            if ((cur&rightBit)==rightBit)                eorAnother^=cur;        }        System.out.println(eorAnother +"and"+ (eorAnother^eor));    }
测试数组：new int[]{1,1,2,2,50,50,50,60,60,60}

以上为(cur&rightBit)==rightBit去宰割a和b，测试后果为：

依照(cur&rightBit)==0条件去宰割a和b，测试后果为：

这两个后果只是，计算出来的先后顺序不同，区别在乎你用什么样的条件，先去找出那个不同位为0的还是为1的。

补充：找两个数的不雷同的最低位

例：a^b≠0，找出a和b二进制数的不雷同的最低位。办法为eor=a^b,eor&(~eor+1)

能够看到，a和b的二进制，在第4位开始不同。

这里自己斗胆提一句：过后在听左老师的课程时，左老师讲的是(cur&rightBit)==0和(cur&rightBit)==1是两个对抗的条件，自己过后没听懂，通过Debug发现，这里左老师说错了，0应该和rightBit是对抗条件，别离找进去，不同位次为1或0的数字。如果大家对这一点有疑难的话，倡议本人Debug，会解答你本人的纳闷，或者评论区一起探讨。

算法真的太美了，心愿大家都能坚持下去!!!!!!