编程之美(寻找丢失的数)

两个题目:

1、给你n个数，其中有且仅有一个数出现奇数次，其余的数都出现偶数次。要求用线性时间常数空间找出出现奇数次的那个数。

2、同样是n个数，其中有且仅有2个数出现奇数次，其余都出现偶数次。要求用线性时间常数空间找出出现奇数次的两个数。

首先知道这个公式就好办了，A^0 = A,A^A =0；

第一题：

int num = 0

 for(遍历所有的数){

num ^ = all[i]

}

        num就是出现一次的数

第二题：

       首先同方法1，得到C = A^B。A，B不等，那么结果不为0。那么二进制中肯定有1。可以先找到那个为1的一位，因为是异或那么可以知道为1的那个位置中，A,B中肯定有一个是0有一个是1。

      则这里可以处理为: 假定k是算出来的那个为1的位置上的数。

       for(遍历所有的数){

if(all[i] ^ k){

num_one  ^= all[i]

}

}

这样num_one就是A,B中的一个。

加入求出来的是A，则可以再用A^B^A求另外一个