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

张开发
• 2026/4/25 8:14:23 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【中等】在其他数都出现偶数次的数组中找到出现奇数次的数－Java：原问题
分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.BitwiseOperation; /** * 在其他数都出现偶数次的数组中找到出现奇数次的数 * * 【题目】 * 给定一个整型数组arr其中只有一个数出现了奇数次其他的数都出现了偶数次打印这个数。 * * 【进阶】 * 有两个数出现了奇数次其他的数都出现了偶数次打印这两个数。 * * 【要求】 * 时间复杂度为O(N)额外空间复杂度为O(1)。 * * 【难度】 * 中等 * * 【解答】 * 整数n与0异或的结果是1整数n与整数n异或的结果是0。所以先申请一个整型变量记为eO。在遍历数组的过程中把eO和每个数 * 异或(eOeO^当前数)最后eO的值就是出现了奇数次的那个数。这是什么原因呢因为异或运算满足交换律与结合律。为了方便说明 * 我们假设ABC这三个数出现了偶数次D这个数出现了奇数次并且出现的顺序为:CBDAABC。因为异或运算满足交换 * 律和结合律所以任意调整异或的顺序也不会改变最终eO的值那么按照原始顺序异或得到的eO结果与按照如下顺序异或出的eO结果 * 是相同的AABBCCD。而按照这个顺序的异或最终结果就是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 */

更多文章