如何快速找出数组中只出现一次的两个数

清疚 2022-08-05 12:15 252阅读 0赞

今天和小伙伴们聊天，聊到一个问题：如何快速找出一个数组中只出现一次的两个数，其他元素出现两次？

直观上，这个可以可以使用一个Map，**Map对应的键值key就是数组中的元素，value就是这个元素出现的次数**。这样我们通过一次遍历数组中的元素，如果元素出现在map中，则将其对应的value加1，否则将元素添加到map中，这样遍历完一遍数组，我们就可以得到数组中每个元素对应出现的次数，然后再通过遍历一遍map，返回value为1对应的key就是我们需要求得元素。

**时间复杂度**：因为首先需要遍历一遍数组，时间开销为O(n)，构建完map后需要遍历一遍map找到value为1的元素，而map的个数为n/2，时间开销为O(n/2)，所以总的时间开销为**O(n)**。

**空间复杂度**：因为需要建立一个map，而且最后map的大小为n/2，所以空间复杂度为**O(n)**。

到这里，可能大家觉得效率已经很好了，毕竟时间复杂度和空间复杂度都是线性的，那这个是不是最优的呢？我们还能不能对时间或者空间进行相应的优化呢？

联想到前面使用位操作“异或”找出数组中只出现一次的一个数，那么两个数的情况可不可以使用这种方法呢？答案是肯定的，分析如下。

1、对于出现两次的元素，使用“异或”操作后结果肯定为0，那么我们就可以遍历一遍数组，对所有元素使用异或操作，那么得到的结果就是两个出现一次的元素的异或结果。

2、因为这两个元素不相等，所以异或的结果肯定不是0，也就是可以再异或的结果中找到1位不为0的位，例如异或结果的最后一位不为0。

3、这样我们就可以最后一位将原数组元素分为两组，一组该位全为1，另一组该位全为0。

4、再次遍历原数组，最后一位为0的一起异或，最后一位为1的一起异或，两组异或的结果分别对应着两个结果。

代码如下：

<span style="white-space:pre">	</span>public int[] getOnceEle(int[] A) {
    		if(A.length < 2)
    			return A;
    	
    		int[] result = new int[2];  //要返回的结果
    		int res = A[0];  //第一次对所有元素进行亦或操作结果
    		for(int i=1; i<A.length; i++) {
    			res ^= A[i];
    		}
    		int bitIndex = 0;
    		for(int i=0; i<32; i++) {  //找出亦或结果为1的位。
    			if((res>>i & 1) == 1) {
    				bitIndex = i;
    				break;
    			}
    		}
    		for(int i=0; i<A.length; i++) { //根据bitIndex为1，将元素分为两组
    			if((A[i] >> bitIndex & 1) == 1)
    				result[0] ^= A[i];   //对应位为1，亦或得到的结果
    			else
    				result[1] ^= A[i];   //对应位为0，亦或得到的结果
    		}
    		
    		return result;
    	}

**时间复杂度：**第一次循环，将所有元素异或得到对应结果，时间开销为O(n)；第二次循环，找出第一次异或结果为1的位，时间开销为O(32)；第三次循环，根据为1的位将元素分为两组进行异或得到两个结果，时间复杂度为O(n)，所以总的时间复杂度为**T(n) = 2\*O(n)+O(32) = O(n)。**

**空间复杂度：**常数，因为只分配了两个空间用于结果的保存，因此**空间复杂度为常数**。

同样的，可以利用位运算找出存在3个只出现一次的元素。因为如果有3个元素只出现一次，那么元素的个数肯定是奇数，这样就可以利用位为1将元素分为两组，如果有一组元素为偶数个，那么这一组对应的元素或者全是出现两次的，或者有两个出现一次的；如果为偶数的组全是出现两次的，那么我们可以再次将为奇数个数的元素利用位进行划分。这样最终就可以求解。