程序员代码面试指南刷题--第七章.在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数

题目描述

给一个数组arr，其中只有一个数出现了奇数次，其它数出现了偶数次，打印这个数。

输入描述:

输出包含两行，第一行包含一个整数n（1≤n≤105）（1 \leq n \leq 10^5）（1≤n≤105），代表数组arr长度，第二行有n个数，代表数组arrarri为32位整数arr_i 为32位整数arri​为32位整数。

输出描述:

输出一个整数，代表出现次数为奇数次的那个数。

示例1

输入

5
3 1 3 1 2

输出

2
           

示例2

输入

3
6 6 3

输出

3
           

解法一：异或

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        String[] ss = br.readLine().trim().split(" ");
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i] = Integer.parseInt(ss[i]);
        }
        getRes(arr);
    }
    public static void getRes(int[] arr){
        if(arr==null||arr.length==0) return;
        int res = 0;
        for(int i=0;i<arr.length;i++){
            res ^= arr[i];
        }
        System.out.println(res);
    }
}
           

进阶问题：假如有两个数的个数为奇数其他数的个数为偶数请找出来

public static void getRes(int[] arr) {
   	int ab = 0,a = 0;
   	for(int i=0;i<arr.length;i++) {
   		ab ^= arr[i];
   	}
   	int firstOne = ab&(~ab+1); //得到第一个1 的位置
   	for(int i=0;i<arr.length;i++) {
   		if((arr[i]&firstOne)!=0) {
   			a ^= arr[i]; 
   		}
   	}
   	System.out.println(a+" "+(ab^a));
   }