136.只出现一次的数字

题目描述

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

要求：以线性时间复杂度和常数空间解决。

示例 1:

输入: nums = [2,2,1]
输出: 1

示例 2:

输入: nums = [4,1,2,1,2]
输出: 4

解题思路：位运算异或

异或的性质：

• 交换律、结合律：a ^ b ^ a == (a ^ a) ^ b。
• 自反：x ^ x = 0。
• 零元：x ^ 0 = x。

将数组所有元素做异或，成对的数两两抵消为 0，最后只剩下唯一的那个数。

算法步骤

1. 设 x = 0。
2. 依次将 x ^= num。
3. 返回 x。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int result = solution.singleNumber(nums);
        System.out.println(result);

        scanner.close();
    }
}

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

复杂度分析

• 时间复杂度：O(n)

  • 单次线性遍历，常数时间的位运算。

• 空间复杂度：O(1)

  • 只使用一个累积变量。

异或 x ^= num