在其他数都出现偶数次的数组中找到出现次数为奇数次的数

参考自程序员代码面试指南

其他数都出现偶数次的数组中找到出现奇数次的数字 整数n与0异或的结果为n，n与n异或的结果为0

代码语言：javascript复制

public void printOddTimesNum1(int[] arrs){
        int eO=0;
        for(int x:arrs){
            eO=eO^x;
        }
        System.out.println(eO);
    }

代码语言：javascript复制

如果只有a和b出现了奇数次，那么最后的eO一定是a^b。如果数组中出现了两个奇数次的数
最终eO一定不等于0。那么肯定可以在32位整数eO上找到一个不为0的bit位。假设是第k位不等于0，
说明a和b的第k位一定是一个是0，一个是1，接下来再设置一个变量记为eHasOne,然后再遍历一次数组。
这次遍历时，eHasOne只和第k位是1的整数异或，其他的数忽略。那么在第二次遍历之后，eHasOne就是a或b中的一个。
eO^eHasOne就是另一个出现奇数次的数。

代码语言：javascript复制

public void printOddTimesNum2(int[] arrs){
        int eO=0,eHasOne=0;
        for(int x:arrs){
            eO=eO^x;
        }
        int rightOne=eO&(~eO 1);
        for(int cur:arrs){
            if((cur&rightOne)!=0){
                eHasOne^=cur;
            }
        }
        System.out.println(eHasOne  " "  eO);
    }

程序员 面试 数组

0 人点赞