【中等】在其他数都出现偶数次的数组中找到出现奇数次的数－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方法。 * * @author Created by LiveEveryDay */ public class InOtherNumAppearEvenArrayFindAppearOddNum1 { public static void printOddTimesNum1(int[] arr) { int eO = 0; for (int cur : arr) { eO ^= cur; } System.out.println(eO); } public static void main(String[] args) { int[] arr = {1, 2, 3, 3, 2, 8, 1}; printOddTimesNum1(arr); } } // ------ Output ------ /* 8 */