程式員代碼面試指南刷題--第七章.在其它數出現次數都為偶數的數組中找到出現次數為奇數次的數

題目描述

給一個數組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));
   }