题解

题面描述

给定一个非空整数数组 $nums$，其中除了某个元素只出现一次以外，其余每个元素均出现两次。要求在 $O(n)$ 的时间复杂度内，且只使用常量级额外空间，找出只出现一次的元素。

思路

利用异或（$XOR$）操作的性质：

• 任意数与自身 $XOR$ 后为 $0$，即 $a\oplus a=0$；
• 任意数与 $0$ $XOR$ 后为自身，即 $a\oplus 0=a$；
• $XOR$ 运算具有交换律和结合律。

遍历数组，将所有数 $XOR$ 在一起，相同的数会被抵消，最后剩下的即为只出现一次的数。

代码分析

• 时间复杂度：遍历一遍数组，时间复杂度为 $O(n)$。
• 空间复杂度：只使用常数个额外变量，空间复杂度为 $O(1)$。
• 问题本质：利用位运算中异或的消除性质，将成对出现的数全部消掉，剩下的数即为目标答案。

C++

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

// 定义Solution类
class Solution {
public:
    // 功能函数：找出数组中只出现一次的数字
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        // 遍历每个数字，利用异或运算抵消成对出现的数
        for (int num : nums) {
            ans ^= num; // ans = ans XOR num
        }
        return ans;
    }
};

int main() {
    int x;
    vector<int> nums;
    // 读入数据，ACM模式下输入的数字以空格或换行分隔
    while (cin >> x) {
        nums.push_back(x);
    }
    // 创建Solution对象，并求解答案
    Solution solution;
    int result = solution.singleNumber(nums);
    // 输出结果
    cout << result << endl;
    return 0;
}

Python

# 功能函数：找出数组中只出现一次的数字
def single_number(nums):
    ans = 0
    # 遍历每个数字，利用异或运算抵消成对出现的数
    for num in nums:
        ans ^= num  # ans = ans XOR num
    return ans

if __name__ == "__main__":
    import sys
    # 读取标准输入数据，按照空格或换行分割
    data = sys.stdin.read().strip().split()
    # 将输入字符串转换为整数列表
    nums = list(map(int, data))
    # 计算结果并输出
    result = single_number(nums)
    print(result)

Java

import java.util.Scanner;

public class Main {
    // 定义Solution类
    static class Solution {
        // 功能函数：找出数组中只出现一次的数字
        public int singleNumber(int[] nums) {
            int ans = 0;
            // 遍历每个数字，利用异或运算抵消成对出现的数
            for (int num : nums) {
                ans ^= num; // ans = ans XOR num
            }
            return ans;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 使用ArrayList存储输入数据
        java.util.ArrayList<Integer> list = new java.util.ArrayList<>();
        while(sc.hasNextInt()){
            list.add(sc.nextInt());
        }
        sc.close();
        // 将ArrayList转换为数组
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++){
            nums[i] = list.get(i);
        }
        // 创建Solution对象，并求解答案
        Solution solution = new Solution();
        int result = solution.singleNumber(nums);
        // 输出结果
        System.out.println(result);
    }
}

题目内容

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

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

输入描述

一个整数数组

输出描述

输出一个整数表示只出现了一次的元素

样例1

输入

2 2 1

输出

1

样例2

输入

4 1 2 1 2

输出

4

样例3

输入

1

输出

1

提示

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