讨论/技术交流/面试题目|求解/

给定一个无序数组 [2,1,3,2,1] 里面中的数有且仅有一个单数(3),其他数字都是成对出现的,请找出唯一不重复数

要求:时间复杂度O(n),空间复杂度O(1)

求问大佬们这题咋解呀🤒🤒

1
共 6 个回复

一般看见这种问题o(1)说明不能往平常的思路去想,那么只有考虑数学的方法,有啥方法可以判断是否俩相等呢?计算机里有个运算叫做异或。 A XOR B XOR B = A XOR 0 = A
所以很简单利用上面这个性质所有数全部异或一下最后的结果就是单数。

8

阿这个题好像用异或^来做,因为只要遇到相同数字异或就会是0,而单数不可能会再有一个数与之异或,所以最后肯定会出现这个单数

1
int ans = 0;
for(auto val : nums) {
    ans ^= val;
}
return ans;
1

剑指56题,是这题的升级版,位运算

1

感觉位运算比较简单,相同数异或得0,遍历一遍,全部异或,剩下的结果就是答案

1