题目描述补充

主元素II

给定一个整数数组，大小为 n，其中除了至多一个元素外，其余每个元素都恰好出现两次。请找出那个只出现一次的元素。

注意：

• 数组中的元素在范围 [-2^31, 2^31 - 1] 内。
• 你可以不使用额外的空间，并且时间复杂度应该优于 O(n^2)。

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解题思路

由于除了一个元素外，其他元素都恰好出现两次，我们可以利用异或（XOR）运算的性质来解这个问题。异或运算满足交换律和结合律，且任何数和0做异或运算结果仍然是原数，任何数和其自身做异或运算结果为0。

因此，我们可以将所有元素进行异或运算，成对出现的元素会因为异或运算而抵消为0，最后剩下的结果就是只出现一次的元素。

PHP 代码示例

function singleNumber($nums) {
    $result = 0;
    foreach ($nums as $num) {
        $result ^= $num;
    }
    return $result;
}

// 测试示例
$nums = [4, 1, 2, 1, 2];
echo singleNumber($nums); // 输出 4

Python 代码示例

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

# 测试示例
nums = [4, 1, 2, 1, 2]
print(singleNumber(nums))  # 输出 4

JavaScript 代码示例

function singleNumber(nums) {
    let result = 0;
    for (let num of nums) {
        result ^= num;
    }
    return result;
}

// 测试示例
const nums = [4, 1, 2, 1, 2];
console.log(singleNumber(nums)); // 输出 4

码小课网站中有更多相关内容分享给大家学习，包括更多算法题解析、数据结构讲解、以及编程技巧分享，帮助大家提升编程能力。