LeetCode 算法：只出现一次的数字 c++

• 原题链接：只出现一次的数字
• 难度：简单⭐️

题目

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

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

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

示例 3 ：
输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 3 * 10⁴
• -3 * 10⁴ <= nums[i] <= 3 * 10⁴
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

位运算

位运算是计算机科学中的一种操作，它直接对整数的二进制位进行操作。位运算符包括以下几种：

1. AND (&)：两个位都为1时，结果为1。
2. OR (|)：两个位中至少有一个为1时，结果为1。
3. XOR (^)：两个位不同的时候结果为1。
4. NOT (~)：反转操作，将1变为0，将0变为1。
5. 左移 (<<)：将数字的所有位向左移动指定的位数。
6. 右移 (>>)：将数字的所有位向右移动指定的位数。

位运算的一些常见用途包括：

• 快速乘除：利用位运算可以快速实现乘以2的幂次方或除以2的幂次方。
• 位掩码：用于提取、设置或清除特定的位。
• 位域：在结构体中使用位域来节省空间。
• 哈希：在某些哈希算法中使用位运算来混合数据。
• 加密：在某些加密算法中使用位运算来混淆数据。

下面是一些位运算的例子：

int a = 12; // 二进制表示: 1100
int b = 13; // 二进制表示: 1101

// AND
int and_result = a & b; // 结果: 1100 (12)

// OR
int or_result = a | b; // 结果: 1101 (13)

// XOR
int xor_result = a ^ b; // 结果: 0001 (1)

// NOT
int not_result = ~a; // 结果: -13 (二进制表示: 10000000000)

// 左移
int left_shift_result = a << 2; // 结果: 48 (二进制表示: 110000)

// 右移
int right_shift_result = b >> 1; // 结果: 6 (二进制表示: 110)

请注意，位运算通常对有符号整数使用算术右移，对无符号整数使用逻辑右移。算术右移会保留符号位，而逻辑右移则不会。

题解

1. 解题思路：位运算法

• 在LeetCode上，有一个经典的算法题叫做“只出现一次的数字”，它的描述是这样的：

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

  • 你可以使用二进制位运算的方式来解决这个问题，因为异或运算具有以下性质：

    1. 对任何数 x ，有 x⊕ x = 0。
    2. 对任何数 x ，有 x ⊕ 0 = x。

• 这意味着，如果我们遍历数组，将每个元素进行异或运算，那么成对出现的元素将会被抵消掉，最终剩下的就是那个只出现一次的元素。

• 下面是用C++实现的核心部分：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

2. c++ demo：

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

int main() {
    // 创建Solution对象
    Solution solution;

    // 测试用例1
    vector<int> nums1 = {2, 2, 1};
    cout << "Test 1: " << solution.singleNumber(nums1) << endl; // 应输出1

    // 测试用例2
    vector<int> nums2 = {4, 1, 2, 1, 2};
    cout << "Test 2: " << solution.singleNumber(nums2) << endl; // 应输出4

    // 测试用例3
    vector<int> nums3 = {1};
    cout << "Test 3: " << solution.singleNumber(nums3) << endl; // 应输出1

    return 0;
}