我是一个甜甜的大橙子🍊,欢迎关注✉️!
我相信技术的力量💪
努力将所学分享给大家😎
你的点赞❤️分享🚀收藏📖就是对我最大的鼓励!
问题
给定一个整型数组nums,除某个元素仅出现1次,其余元素都出现3次,找出并返回只出现了1次的元素。
约束条件
1 <= nums.length <= 3 * 10 ** 4
-2 ** 31 <= nums[i] <= 2 ** 31 – 1 (**表示幂)
示例一:
输入:nums = [2,2,2,3]
输出:3
示例二:
输入:nums = [4,4,6,6,4,5,6]
输出:5
解题思路
整体思路: 通过与数组中元素的二进制位一位一位的比较,找到某一位有且唯一不同的元素。
这道题涉及到位运算,通过与运算&
,移位<<
,一起异或^
找到指定元素,可以先了解位运算相关基础知识。
- 通过
bit = 1 << i
结合i
循环实现,<<
是左移位,bit
用来与数组元素进行比较。 - 进入第
i
次循环,bit
的第i
位是1,其余都是0,此时循环数组中的元素,如果数组元素与bit
的第i
位相同,count
计数加一,数组循环结束后:
– 如果count % 3 ==0
,说明该位相同的数是3的整数倍个,因此要找的元素这一位不是1
– 如果count % 3 ==1
,说明该位相同的数不是3的整数倍个,因此要找的元素这一位是1 - 确定该元素的第
i
位是0或1之后,bit
就要移位进行下一次的比较了,因此我们要把刚才的结果存起来,这时候就要用到异或^
,设置一个二进制位全为0的临时变量tmp
,0和0异或为0、0个1异或为1,这样就能存下来了。 - exp:[1,1,1,0,0,0,3,3,3,4]
– 比较数组元素二进制第0位,有6个是1,4个是0,count = 6
说明单独的这个数第0位不是1而是0,tmp
不需要变化;
– 再比较第1位,有3个是1,7个是0,count = 3
说明单独的这个数第1位不是1而是0,tmp
不需要变化;
– 再比较第2位,有1个是1,9个是0,count = 1
说明单独的这个数第2位是1,tmp
与此时的bit
异或。
– …一直比较到第31位
最后我们得到的tmp
就是那个单独存在的元素。
代码实现
class Solution(object):
def findNumber(self, nums):
tmp = 0
for i in range(32):
count = 0
bit = 1 << i # 1,10,100,1000...
print(f'bit:{bin(bit)}')
for num in nums:
print(f'num:{bin(num)}')
if num & bit:
count += 1
print(f'count:{count}')
if count %3 != 0:
tmp ^= bit
print(f'tmp:{bin(tmp)}')
return tmp
s = Solution()
nums = [1,2,1,2,1,4,2]
ans = s.findNumber(nums)
print(ans)
公众号:一个甜甜的大橙子
知识星球:知识的朋友
欢迎交流~~
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/63056.html