欢迎光临散文网 会员登陆 & 注册

数组中只出现一次的数字查找,其他数字出现两次

2023-03-07 15:56 作者:秋名山西  | 我要投稿

先贴代码:

解题思路:

    利用异或的原理进行解题,其相同的元素异或的结果为0,0和任何元素异或得到的结果都是任何元素。

对于找出一个元素的情况,直接将整个数组从头到尾异或就可以得出答案。

对于需要找出两个的情况,就需要以下步骤:

1、先求处整个数组异或的结果eor;

2、利用eor和其自身的补码(eor取反+1)进行按位与,得出将数组拆分的标志(需要说明的是:该标志其实就是一个某个bit位为1,其他位为0的数值,只要对应bit位不为1,按位与的结果都将是0);

3、利用2中得出的标志位,在对数组进行遍历的循环中,让数组元素与标志位进行按位与,对结果为0的数组元素进行异或,异或最终的结果就是我所查找的只出现一次的元素之一。

4、将3中的到元素结果与1中的异或结果再进行异或,得到所查找的两个数中的另一个

数组中只出现一次的数字查找,其他数字出现两次的评论 (共 条)

分享到微博请遵守国家法律