问题描述

给定一个整数数组，数组中所有元素都出现了两次，只有一个数字出现了一次。需要找出这个只出现一次的数字

示例

int[] n = new int[]{1, 1, 2, 2, 3, 4, 4, 5, 5};

输出：3

解题思路

1. 使用异或运算的性质

异或（XOR）运算有以下几个性质：

  • a ^ a = 0 ：同样的数字异或的结果是 0
  • a ^ 0 = a ：任意数字与 0 异或结果是它本身
  • a ^ b = b ^ a ：异或运算满足交换律
  • a ^ (b ^ c) = (a ^ b) ^ c ：异或运算满足结合律

2. 解决方法

基于以上性质，可以使用异或运算来抵消成对出现的数字，最终得到那个只出现一次的数字。具体步骤如下：

  • 遍历数组中的所有元素，对每个元素进行异或操作
  • 因为成对出现的数字会互相抵消（a ^ a = 0），最后只会剩下那个单独出现的数字

代码实现

SingleNumber.java 
public class SingleNumber {
    public static void main(String[] args) {
        // 输入数组
        int[] n = new int[]{1, 1, 2, 2, 3, 4, 4, 5, 5};
        
        // 用于存储最终结果
        int ans = 0;

        // 遍历数组进行异或操作
        for (int i = 0; i < n.length; ++i) {
            ans ^= n[i];
        }

        // 输出结果
        System.out.println(ans);  // 输出：3
    }
}
SingleNumber.c 
#include <stdio.h>

int main() {
    // 输入数组
    int n[] = {1, 1, 2, 2, 3, 4, 4, 5, 5};
    int length = sizeof(n) / sizeof(n[0]);
    
    // 用于存储最终结果
    int ans = 0;

    // 遍历数组并进行异或操作
    for (int i = 0; i < length; ++i) {
        ans ^= n[i];
    }

    // 输出结果
    printf("The number that appears once is: %d\n", ans);  // 输出：3

    return 0;
}

性能分析

1. 时间复杂度

  • O(n)：只需要遍历一遍数组，对每个元素进行常数时间的异或操作，因此时间复杂度为 O(n)，其中 n 为数组的长度

2. 空间复杂度

  • O(1)：只使用了一个额外的变量 ans 来存储结果，因此空间复杂度是常数 O(1)，没有使用任何额外的存储空间