一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
知识点:异或操作,任何数与本身异或等于0 异或就是同为0,异为1.
位运算 << 左移一位,二进制10 (10<<1)——>(100) >>右移一位
判断两个只出现了一次的数字,先将所有元素异或操作,结果为两个只出现一次的的元素异或的结果,找出sum的第一位为1的数字,(两个不一样的数字一定有某些位置数字不一样,找出第一个不一样的数字),以这个位置将元素分为两部分,一部分该位置是一种,另一部分是另一种,完成两部分的分隔,此时每一部分包含一个单次元素,将两部分分别全部异或操作,结果就是所求元素。
public class 数组中只出现一次的数字 { public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { //判断长度 if(array == null || array.length <= 1){ num1[0] = num2[0] = 0; return; } //定义变量 int len = array.length, index = 0, sum = 0; //数组所有元素异或操作,结果为两个只出现一次的元素的异或 for(int i = 0; i < len; i++){ sum ^= array[i]; } System.out.println("sum:"+sum); //<<位运算符 左移一位 二进制 10左移变成100,找到第一个1 for(index = 0; index < 32; index++){ if((sum & (1 << index)) != 0) break; } System.out.println("index:"+index); for(int i = 0; i < len; i++){ if((array[i] & (1 << index))!=0){ num2[0] ^= array[i]; }else{ System.out.println(array[i]); num1[0] ^= array[i]; } } System.out.println(num1[0]+" "+num2[0]); } public static void main(String[] args) { int[] a = {3,3,4,4,5,5,6,6,7,8,8,44,99,99}; int[] num1 = new int[1]; int[] num2 = new int[1]; FindNumsAppearOnce(a,num1,num2); } }