异或运算--01---arr中，只有一种数出现了K次，其他数都出现了M次

提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录异或运算题体系--01---异或运算需求:一个数组中有一种数出现K次,其他数都出现了M次,M1,KM.要求:如果这个数出现了K次,返回这个数,如果这个数出现次数不等于K,返回-1分析1. new1一个32位的数组t2. 把目标数组arr,每一个元素,分解成一个32位的 二进制数,并用数组t,记录每一位的1出现的次数3. 数组t现在相当于是 一个 32位容器,每一个位都装了,目标数组,所有元素,相同位数下的1的数据和.4.数组t的每一位,取模m,5.临界值0的情况是解法代码对数器1.用map来求此问题2 随机造数全部代码异或运算题体系–01—异或运算需求:一个数组中有一种数出现K次,其他数都出现了M次,M1,KM.要求:如果这个数出现了K次,返回这个数,如果这个数出现次数不等于K,返回-1额外空间复杂度o(1),时间复杂度o(N)分析1. new1一个32位的数组t2. 把目标数组arr,每一个元素,分解成一个32位的 二进制数,并用数组t,记录每一位的1出现的次数t[0] 0位置的1出现了几个t[1] 1位置的1出现了几个t[i] i位置的1出现了几个…int[]tnewint[32];// t[0] 0位置的1出现了几个// t[i] i位置的1出现了几个for(intnum:arr){for(inti0;i31;i){t[i](numi)1;}}3. 数组t现在相当于是 一个 32位容器,每一个位都装了,目标数组,所有元素,相同位数下的1的数据和.4.数组t的每一位,取模m,如果t[i] % m 0,表示我们要找的出现K次数,分解成32位二进制数时,在i位置上,是0t[i] % m ! 0,表示我们要找的出现K次数,分解成32位二进制数时,在i位置上,是1如果t[i] % m k如果取模结果等于k,表名这个出现K次数存在,我们就记录他的位置.ans | (1 i);---------用int ans 0;亦或 (1 i) 来保存如果取模结果t[i] % m ! k如果取模结果不等于k,表名这个数出现次数不等于K,返回-1return -1;intans0;for(inti0;i32;i){if(t[i]%m!0){if(t[i]%mk){ans|(1i);}else{return-1;}}}5.临界值0的情况是0是特殊情况,因为0,分解成32位2进制数时,任何位置上都是0,0数组里出现多少次都不走上述-1那条逻辑链所以 0 这个数的出现的次数 要最后再判断一下,是不是等于K次if(ans0){intcount0;for(intnum:arr){if(num0){count;}}if(count!k){return-1;}}解法代码// 请保证arr中只有一种数出现了K次其他数都出现了M次publicstaticintonlyKTimes(int[]arr,intk,intm){int[]tnewint[32];// t[0] 0位置的1出现了几个// t[i] i位置的1出现了几个for(intnum:arr){for(inti0;i31;i){t[i](numi)1;}}intans0;for(inti0;i32;i){if(t[i]%m!0){if(t[i]%mk){ans|(1i);}else{return-1;}}}if(ans0){intcount0;for(intnum:arr){if(num0){count;}}if(count!k){return-1;}}returnans;}对数器1.用map来求此问题key来记录目标数组的元素的值value 来记录key元素出现的次数publicstaticinttest(int[]arr,intk,intm){HashMapInteger,IntegermapnewHashMap();for(intnum:arr){if(map.containsKey(num)){map.put(num,map.get(num)1);}else{map.put(num,1);}}for(intnum:map.keySet()){if(map.get(num)k){returnnum;}}return-1;}2 随机造数publicstaticvoidmain(String[]args){intkinds5;intrange30;inttestTime100000;intmax9;System.out.println(测试开始);for(inti0;itestTime;i){inta(int)(Math.random()*max)1;// a 1 ~ 9intb(int)(Math.random()*max)1;// b 1 ~ 9intkMath.min(a,b);intmMath.max(a,b);// k mif(km){m;}int[]arrrandomArray(kinds,range,k,m);intans1test(arr,k,m);intans2onlyKTimes(arr,k,m);if(ans1!ans2){System.out.println(ans1);System.out.println(ans2);System.out.println(出错了);}}System.out.println(测试结束);}publicstaticint[]randomArray(intmaxKinds,intrange,intk,intm){intktimeNumrandomNumber(range);// 真命天子出现的次数inttimesMath.random()0.5?k:((int)(Math.random()*(m-1))1);// 2intnumKinds(int)(Math.random()*maxKinds)2;// k * 1 (numKinds - 1) * mint[]arrnewint[times(numKinds-1)*m];intindex0;for(;indextimes;index){arr[index]ktimeNum;}numKinds--;HashSetIntegersetnewHashSet();set.add(ktimeNum);while(numKinds!0){intcurNum0;do{curNumrandomNumber(range);}while(set.contains(curNum));set.add(curNum);numKinds--;for(inti0;im;i){arr[index]curNum;}}// arr 填好了for(inti0;iarr.length;i){// i 位置的数我想随机和j位置的数做交换intj(int)(Math.random()*arr.length);// 0 ~ N-1inttmparr[i];arr[i]arr[j];arr[j]tmp;}returnarr;}// [-range, range]publicstaticintrandomNumber(intrange){return(int)(Math.random()*(range1))-(int)(Math.random()*(range1));}全部代码packagemain.java.month1;importjava.util.HashMap;importjava.util.HashSet;publicclassclass04{publicstaticinttest(int[]arr,intk,intm){HashMapInteger,IntegermapnewHashMap();for(intnum:arr){if(map.containsKey(num)){map.put(num,map.get(num)1);}else{map.put(num,1);}}for(intnum:map.keySet()){if(map.get(num)k){returnnum;}}return-1;}// 请保证arr中只有一种数出现了K次其他数都出现了M次publicstaticintonlyKTimes(int[]arr,intk,intm){int[]tnewint[32];// t[0] 0位置的1出现了几个// t[i] i位置的1出现了几个for(intnum:arr){for(inti0;i31;i){t[i](numi)1;}}intans0;for(inti0;i32;i){if(t[i]%m!0){if(t[i]%mk){ans|(1i);}else{return-1;}}}if(ans0){intcount0;for(intnum:arr){if(num0){count;}}if(count!k){return-1;}}returnans;}publicstaticint[]randomArray(intmaxKinds,intrange,intk,intm){intktimeNumrandomNumber(range);// 真命天子出现的次数inttimesMath.random()0.5?k:((int)(Math.random()*(m-1))1);// 2intnumKinds(int)(Math.random()*maxKinds)2;// k * 1 (numKinds - 1) * mint[]arrnewint[times(numKinds-1)*m];intindex0;for(;indextimes;index){arr[index]ktimeNum;}numKinds--;HashSetIntegersetnewHashSet();set.add(ktimeNum);while(numKinds!0){intcurNum0;do{curNumrandomNumber(range);}while(set.contains(curNum));set.add(curNum);numKinds--;for(inti0;im;i){arr[index]curNum;}}// arr 填好了for(inti0;iarr.length;i){// i 位置的数我想随机和j位置的数做交换intj(int)(Math.random()*arr.length);// 0 ~ N-1inttmparr[i];arr[i]arr[j];arr[j]tmp;}returnarr;}// [-range, range]publicstaticintrandomNumber(intrange){return(int)(Math.random()*(range1))-(int)(Math.random()*(range1));}publicstaticvoidmain(String[]args){intkinds5;intrange30;inttestTime100000;intmax9;System.out.println(测试开始);for(inti0;itestTime;i){inta(int)(Math.random()*max)1;// a 1 ~ 9intb(int)(Math.random()*max)1;// b 1 ~ 9intkMath.min(a,b);intmMath.max(a,b);// k mif(km){m;}int[]arrrandomArray(kinds,range,k,m);intans1test(arr,k,m);intans2onlyKTimes(arr,k,m);if(ans1!ans2){System.out.println(ans1);System.out.println(ans2);System.out.println(出错了);}}System.out.println(测试结束);}}