首页 > 其他 > 详细

给出2n+1个数,其中有2n个数出现过两次,如何用最简便的方法找出里面只出现了一次的那个数(转载)

时间:2014-06-25 22:23:56      阅读:391      评论:0      收藏:0      [点我收藏+]

有2n+1个数,其中有2n个数出现过两次,找出其中只出现一次的数 

例如这样一组数3,3,1,2,4,2,5,5,4,其中只有1出现了1次,其他都是出现了2次,如何找出其中的1?

最简便的方法是使用异或,代码如下:

public class XOR {  
    public static void main(String[] args){  
        int[] arr={3,3,1,2,4,2,5,5,4};  
        int res=0;//初始值   
        for(int i=0;i<arr.length;i++){  
            res ^=arr[i];  
        }  
        System.out.println(res);  
    }  
}  

 

运行结果:

1

算法的原理就是:任何数异或0值不变,任何数与自己异或值为0。  

异或的规则为:如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0  (需要转换为二进制计算)

因此一个数两次异或同一个数,值不变。

给出2n+1个数,其中有2n个数出现过两次,如何用最简便的方法找出里面只出现了一次的那个数(转载),布布扣,bubuko.com

给出2n+1个数,其中有2n个数出现过两次,如何用最简便的方法找出里面只出现了一次的那个数(转载)

原文:http://www.cnblogs.com/liaokailin/p/3804517.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!