【中等】在其他数都出现偶数次的数组中找到出现奇数次的数－Java：进阶问题

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.BitwiseOperation; /** * 在其他数都出现偶数次的数组中找到出现奇数次的数 * * 【题目】 * 给定一个整型数组arr，其中只有一个数出现了奇数次，其他的数都出现了偶数次，打印这个数。 * * 【进阶】 * 有两个数出现了奇数次，其他的数都出现了偶数次，打印这两个数。 * * 【要求】 * 时间复杂度为O(N)，额外空间复杂度为O(1)。 * * 【难度】 * 中等 * * 【解答】 * 整数n与0异或的结果是1，整数n与整数n异或的结果是0。所以，先申请一个整型变量，记为eO。在遍历数组的过程中，把eO和每个数 * 异或(eO=eO^当前数)，最后eO的值就是出现了奇数次的那个数。这是什么原因呢？因为异或运算满足交换律与结合律。为了方便说明， * 我们假设A，B，C这三个数出现了偶数次，D这个数出现了奇数次，并且出现的顺序为:C，B，D，A，A，B，C。因为异或运算满足交换 * 律和结合律，所以任意调整异或的顺序也不会改变最终eO的值，那么按照原始顺序异或得到的eO结果与按照如下顺序异或出的eO结果 * 是相同的：A，A，B，B，C，C，D。而按照这个顺序的异或最终结果就是D。也就是说，先异或还是后异或某一个数，对最终的结果是 * 没有任何影响的，最终结果等同于连续异或同一个出现偶数次的数之后，再连续异或下一个出现偶数次的数，等到所有出现偶数次的数 * 异或完，异或结果肯定是0，最后再去异或出现奇数次的数，最终结果自然是出现奇数次的数。所以对任何排列的数组，只要这个数组 * 有一个数出现了奇数次，另外的数出现了偶数次，最终异或结果都是出现了奇数次的数。 * 请参看printOddTimesNum1方法。 * * 如果只有a和b出现了奇数次，那么最后的异或结果eO就是a^b。所以，如果数组中有两个出现了奇数次的数，最终的eO一定不等于0。 * 那么肯定能在32位整数eO上找到一个不等于0的bit位，假设是第k位不等于0。eO在第k位不等于0，说明a和b的第k位肯定一个是1另 * 一个是0。接下来再设置一个变量记为eOhasOne，然后再遍历一次数组。在这次遍历时，eOhasOne只与第k位上是1的整数异或，其 * 他的数忽略。那么在第二次遍历结束后，eOhasOne就是a或者b中的一个，而eO^eOhasOne就是另外一个出现奇数次的数。 * 请参看printOddTimesNum2方法。 * * @author Created by LiveEveryDay */ public class InOtherNumAppearEvenArrayFindAppearOddNum2 { public static void printOddTimesNum2(int[] arr) { int eO = 0, eOhasOne = 0; for (int curNum : arr) { eO ^= curNum; } int rightOne = eO & (~eO + 1); for (int cur : arr) { if ((cur & rightOne) != 0) { eOhasOne ^= cur; } } System.out.println(eOhasOne + " " + (eO ^ eOhasOne)); } public static void main(String[] args) { int[] arr = {1, 2, 3, 3, 2, 8, 1, 6}; printOddTimesNum2(arr); } } // ------ Output ------ /* 6 8 */