【程序员代码面试指南】特殊数组中找到出现次数是奇数次的数

题目描述

• 给一个数组arr，其中只有一个数出现了奇数次，其它数都出现了偶数次，打印这个数。
• 输入描述：第一行包含一个整数n（1<=n<=10^5），代表数组arr长度；第二行是n个数，代表数组元素arr_i（32位整数）。
  输入：
  5
  3 1 3 1 2
• 输出描述：输出一个整数，代表出现次数为奇数次的数。输出：2
• 备注：时间复杂度O(n)，额外空间复杂度O(1)。
• 考点：位运算

解题思路

异或（位相同异或值是0，位不同异或值是1）运算满***换律和结合律，两个相同的数异或值是0，三个相同的数异或值是其本身。由此可得，数组中出现次数是偶数次的数异或值是0，而出现次数是奇数次的数异或值是其本身。例如：2 3 5 2 5，2（0010）与3（0011）异或值是1（0001），1（0001）与5（0101）异或值是4（0100），4（0100）与2（0010）异或值是6（0110），6（0110）与5（0101）异或值是3（0011）。其中，数组中2出现次数是两次，3出现次数是一次，5出现次数是两次。

Java (javac 1.8)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);  // 输入
        while (input.hasNext()) {
            int length = input.nextInt();  // 输入数组长度
            int arr[] = new int[length];
            int num = 0;  // 任何数num与0异或值依然是num
            for (int i = 0; i < length; i++) {
                arr[i] = input.nextInt();  // 输入数组元素值
                num = num ^ arr[i];  // 将数组每一个元素都与num异或
            }
            System.out.println(num);  // 输出num，即是数组中出现次数为奇数次的数
        }
    }
}