首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

一个整型数组里去除两个数字之外,其他的数字都出现了两次,请写程序找出这两个只出现一次的数字

2012-10-10 
一个整型数组里除了两个数字之外,其他的数字都出现了两次,请写程序找出这两个只出现一次的数字首先来一道

一个整型数组里除了两个数字之外,其他的数字都出现了两次,请写程序找出这两个只出现一次的数字

首先来一道简单的题目:一个数组中,除了一个数字,其他数字都出现了两次,我们如何找出那个不同的数字,

很简单,将所有的数字都异或,那么最终结果就是要找的数字,因为相同的数字异或结果就是0

那么现在来思考这个题目:

《编程之美》一书提供了一种方法,即将所有的数字进行一个异或,得到一个数字,然后以该数字的某非0为作为过滤位,将数组分为两个部分,此时出现一次的数字会分到不同的部分,现在的问题就已经转换为出现一次的情况:

算法如下:

public int[]findTwoDiff(int[]a){int []result=new int[2];int temp=0;int flag=1;for(int t:a){temp^=t;}while((temp&flag)==0){flag<<=1;}for(int t:a){if((t&flag)==1){result[0]^=t;}else{result[1]^=t;}}return result;}


 

1楼xymyp5天前 12:36
武汉纺织大学??

热点排行