闯关leetcode——136. Single Number

题目

地址

内容

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 3 * 10⁴
• -3 * 10⁴ <= nums[i] <= 3 * 10⁴
• Each element in the array appears twice except for one element which appears only once.

解题

这题主要考察“异或”操作。
异或操作具有以下几个性质：

• 自反性：x ^ y ^ y = x
• 结合性：(x ^ y) ^ z = x ^ (y ^ z)
• 与数字0异或无变化：x ^ 0 = x

因为x ^ x =0，这样偶数个x就会得到结果0；而x ^ 0 = x，这样会让单个的x得以保留。所以这题的思路就是对所有数字进行异或操作。

#include <vector>
using namespace std;

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

代码地址

https://github.com/f304646673/leetcode/tree/main/136-Single-Number/