找出数组中只出现一次的数


今天来看一道有意思的题,看起来很简单,但是要想到满足要求的答案没那么容易。


有一个非空整形数组,除了有一个只出现过一次的数,其他的数都出现且只出现过两次,现要求找出这个只出现过一次的数。时间复杂度不能超过 O(n),而且不能使用额外空间。


大概意思就是,比如从 [5,5,8,8,6,9,9] 数组中找出 6 这个只出现过一次的数。


本来可以想到对数组先进行排序,再遍历数组判断当前元素和前后元素是否相同,从而来找出那个只出现一次的元素。


但是题目要求时间复杂度不能超过 O(n),且空间复杂度为 O(1),因此数组排序不满足要求。


看来这道题需要使用点技巧了,我们使用位运算来试试。


遍历数组,对每个元素都进行异或运算。因为数组中其他的元素都出现过两次,两个相同元素的异或运算结果为 0,而 0 和其他元素的异或运算结果为该元素本身,所以遍历数组最后只剩下那个只出现一次的那个元素。


注意位运算都是指基于二进制的运算,所以一个异或运算其实是先把十进制数转化为二进制,然后再去做异或运算的。


这种位运算符合题目的要求,只需遍历一遍数组即可,时间复杂度为 O(n),也不需要额外的空间。


我们再来看一下具体的例子,来个简单一点的数组,[2,2,8,3,3],通过异或运算找出 8 这个数。


先把数组中的元素全部转换成二进制,分别为:


#十进制转二进制

2 -> 10 2 -> 10 8 -> 1000 3 -> 11 3 -> 11



接下来依次对二进制数做异或运算,异或运算符号为 "^", 分别为:


#二进制数异或运算

10 ^ 10 = 0 0 ^ 1000 = 1000 1000 ^ 11 = 1011 1011 ^ 11 = 1000



(注意,如果参与异或运算的两个值位数不一致的话,前面补0)


也就是说最终我们得到的是二进制数 1000,对应的十进制就是数字 8。


这道题非常巧妙的利用了异或运算的特点,两个相同的数异或结果为 0,所以数组中相同的两个数都相互异或为 0 了,只剩下那个只出现一次的数。


下面是一段 python 实现的代码,利用异或运算找出只出现一次的数。

	

#文章来源于 公众号 【谭某人】

#python 利用异或运算找出数组中只出现一次的数 d

ef singleNumber(nums):

        res = 0

        for num in nums:            

            res ^= num                    return res



关键词: 算法

网友留言(0条)

发表评论