LeetCode 只出现一次的数字题解

LeetCode 只出现一次的数字题解

题目描述

给定一个整数数组，除了某个元素只出现一次外，其余每个元素均出现两次。找出那个只出现一次的元素。

示例：

输入：nums = [2,2,1]
输出：1

输入：nums = [4,1,2,1,2]
输出：4

解题思路

方法：位运算（异或）

思路：

• 使用异或运算来解决这个问题。
• 异或运算满足交换律和结合律。
• 相同的数字异或结果为 0，任何数字与 0 异或结果为自身。
• 将数组中所有数字进行异或运算，结果就是只出现一次的数字。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。
• 空间复杂度：O(1)。

代码实现

方法：位运算（异或）

# 只出现一次的数字（位运算） def single_number(nums): result = 0 for num in nums: result ^= num return result # 测试 def test_single_number(): nums = [2, 2, 1] print(single_number(nums)) # 输出：1 nums = [4, 1, 2, 1, 2] print(single_number(nums)) # 输出：4 if __name__ == "__main__": test_single_number()

测试用例

测试用例 1：基本情况1

输入：nums = [2,2,1]
输出：1

测试用例 2：基本情况2

输入：nums = [4,1,2,1,2]
输出：4

总结

只出现一次的数字是一个经典的位运算问题，它可以通过异或运算来高效地解决。

异或运算的核心思想是：相同的数字异或结果为 0，任何数字与 0 异或结果为自身。

掌握异或运算的使用方法，对于解决类似的问题非常重要。