前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >在其他数都出现偶数次的数组中找到出现次数为奇数次的数

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

作者头像
发布2019-02-25 14:56:13
7930
发布2019-02-25 14:56:13
举报
文章被收录于专栏:WD学习记录

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

其他数都出现偶数次的数组中找到出现奇数次的数字 整数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);
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年09月12日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档