当前位置: 面试刷题>> 主元素Ⅱ (经典算法题500道)


题目描述补充

主元素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

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

推荐面试题