购买备案域名/seo优化工具

一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数。

思路:对数组所有的数进行异或运算,偶数个数的数异或结果为0,将这两个要找的数标记为A、B,也就是最终结果为A、B异或的结果,此时取出右边第一个1,A、B在此位置的值不相同,一个为1,另一个为0,根据这个特点将这些数据分为两两组,分别异或.

import java.util.Arrays;public class SearchOddTimesNumber {public int searchOddTimesNumber(int [] arr){int len = arr.length;int ab = arr[0];for(int i = 1;i < len;i++){ab = ab ^ arr[i];}return ab;}public int ExtractRightOne(int ab){int ab_r1 = ab & ((~ab) +1); //提取最右侧的1//        System.out.println(ab_r1 + "最右侧的1为：" + ab_r1);return ab_r1;}public int searchInab(int[] arr,int ab_r1){int len = arr.length;int a = 0;for(int i = 0;i < len;i++){if((arr[i] & ab_r1) == 0){ //arr[i在该位置没有1，得到的结果为0//按位与&：有0就为0，全1才为1a = a ^ arr[i];}}return a;}public static void main(String[] args) {int[] arr = new int[] {1,1,2,2,3,4,5,6,6,5,4,3,7,6,7,8,9,9,8,9};SearchOddTimesNumber searchOddTimesNumber = new SearchOddTimesNumber();int ab = searchOddTimesNumber.searchOddTimesNumber(arr); //数组arr中的所有数做异或，得到a^bint ab_r1 = searchOddTimesNumber.ExtractRightOne(ab); // 找a^b最右侧的1int a = searchOddTimesNumber.searchInab(arr,ab_r1); // 找到ab中的一个数int b = a ^ ab; // ab中的另一个数System.out.println("数组为：" + Arrays.toString(arr)); // 打印数组System.out.println("数组中存在的两个出现奇数次的数为：" + a + "和" + b);}
}

输出

数组为：[1, 1, 2, 2, 3, 4, 5, 6, 6, 5, 4, 3, 7, 6, 7, 8, 9, 9, 8, 9]
数组中存在的两个出现奇数次的数为：6和9