首页 > 代码库 > 给出2n+1个数,其中有2n个数出现过两次,如何用最简便的方法找出里面只出现了一次的那个数(转载)
给出2n+1个数,其中有2n个数出现过两次,如何用最简便的方法找出里面只出现了一次的那个数(转载)
有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 (需要转换为二进制计算)
因此一个数两次异或同一个数,值不变。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。