只出现一次的数字

题目要求

给定一个非空的整数数组nums，其中有一个元素只出现一次，其他元素都恰好出现两次。要求找出并返回那个只出现了一次的元素。

解题算法必须满足以下条件：

时间复杂度为线性（O(n)），即只能遍历数组一次。
空间复杂度为常量（O(1)），即算法在处理过程中只能使用固定大小的额外空间。

解题思路

要在线性时间内解决问题，并且只使用常量空间，可以使用位运算中的异或（XOR）操作。异或操作有以下几个性质：

任何数和 0 做异或运算，结果仍然是原来的数，即a ^ 0 = a。
任何数和其自身做异或运算，结果是 0，即a ^ a = 0。
异或运算满足交换律和结合律，即a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b。

根据以上性质，我们可以通过一次遍历数组，对数组中的所有元素进行异或运算。由于数组中除了一个元素只出现一次以外，其他元素都出现两次，那么出现两次的元素异或运算的结果会是 0，最终剩下的结果就是只出现一次的那个元素。

具体步骤如下：

初始化一个变量，用于存储异或运算的结果，初始值为 0。
遍历数组nums，对每个元素进行异或运算，即result ^= nums[i]。
遍历完成后，result中存储的就是只出现一次的元素。

这种方法之所以有效，是因为异或运算能够消除成对的相同数字，最终留下的就是那个唯一的、未成对的数字。

Golang 版本

package main

import "fmt"

func singleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result ^= num
    }
    return result
}

func main() {
    nums := []int{4, 1, 2, 1, 2}
    fmt.Println("The single number is:", singleNumber(nums))
}

C++版本

#include <iostream>
#include <vector>

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

int main() {
    std::vector<int> nums = {4, 1, 2, 1, 2};
    std::cout << "The single number is: " << singleNumber(nums) << std::endl;
    return 0;
}

Python 版本

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

if __name__ == "__main__":
    nums = [4, 1, 2, 1, 2]
    print("The single number is:", single_number(nums))

Java 版本

public class Solution {
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 2, 1, 2};
        System.out.println("The single number is: " + singleNumber(nums));
    }
}

Rust 版本

fn single_number(nums: Vec<i32>) -> i32 {
    nums.iter().fold(0, |acc, &x| acc ^ x)
}

fn main() {
    let nums = vec![4, 1, 2, 1, 2];
    println!("The single number is: {}", single_number(nums));
}

总结

上述问题的解决方案是利用异或运算的性质来找出数组中唯一一个只出现一次的元素。异或运算（XOR）有几个关键性质：任何数与 0 异或仍然为自己，任何数与自己异或结果为 0，且异或运算满足交换律和结合律。

在各个版本的代码中（Go, C++, Python, Java, Rust），核心算法都是通过一个变量来累积数组中所有元素的异或结果。由于数组中的元素除了一个单独的数字外，其他数字都是成对出现的，成对的数字异或结果为 0，因此遍历完整个数组后，累积变量中的值即为那个唯一出现一次的数字。

具体步骤如下：

初始化一个变量用于存储结果，初始值为 0。
遍历数组中的每个元素，将其与结果变量进行异或运算。
遍历结束后，结果变量中存储的值即为只出现一次的元素。

这种方法的时间复杂度为 O(n)，因为我们只需要遍历数组一次。空间复杂度为 O(1)，因为我们只使用了一个额外的变量来存储结果，不依赖于输入数组的大小。因此，这种方法满足了题目要求的线性时间复杂度和常量空间复杂度的条件。

hot-100