[LeetCode] #136 只出现一次的数字
发布人：shili8
发布时间：2024-12-24 01:28
阅读次数：0
**只出现一次的数字**
**题目描述**
给定一个非空整数数组，只有一个元素出现了奇数次，其他所有元素都出现了偶数次。请找出这个唯一出现奇数次的元素。
**示例1**
输入: [2,2,3,2]
输出:3**示例2**
输入: [-1,-1,0,0,1,1]
输出: -1**示例3**
输入: [5,7,3,9,2,5,8,6,6,9,7,7]
输出:8**解决方案**
我们可以使用位运算来解决这个问题。由于所有元素都出现了偶数次，除了一个元素外，我们可以将所有元素的二进制表示中的1 位全部清零。
def singleNumber(nums): result =0 for num in nums: # 将当前数字的二进制表示中的1 位设置为结果中对应的位 result ^= num return result
**解释**
这个解决方案使用了位运算来实现。我们将所有元素的二进制表示中的1 位全部清零，剩下唯一出现奇数次的元素。
**时间复杂度**
该解决方案的时间复杂度为 O(n)，其中 n 是数组中元素的数量。
**空间复杂度**
该解决方案的空间复杂度为 O(1)，因为我们只使用了常数大小的额外空间。
**测试用例**
我们可以使用以下测试用例来验证这个解决方案：
print(singleNumber([2,2,3,2])) # 输出:3print(singleNumber([-1, -1,0,0,1,1])) # 输出: -1print(singleNumber([5,7,3,9,2,5,8,6,6,9,7,7])) # 输出:8
**总结**
这个解决方案使用位运算来找出只出现一次的数字。它的时间复杂度为 O(n)，空间复杂度为 O(1)。
粤公网安备 44011102002787号