算法|2.异或运算

1.不用额外变量交换两个数的值

题意：不用额外变量交换（数组中）两个数的值

解题思路：

  • 使用异或运算的性质

代码及运行结果：

2.找到唯一出现奇数次的数字

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

解题思路：

  • 说明：补码的补码即相反数的补码等于原数补码连同符号位取反末尾加
  • 将数组中的数全部异或一遍，得到的即是结果

核心代码：

//arr中，只有一种数出现奇数次public static void printOddTimesNum1(int[] arr){int ero=0;for (int cur:arr) {ero^=cur;}System.out.println("出现奇数次的数字分别是："+ero);}

测试方法：

说明，本题和下一题均为写对数器，并且测试方法在同一个main方法中写着呢。故下边不再写该部分内容。

//for testpublic static void main(String[] args) {int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };//System.out.println("预期结果："+2);printOddTimesNum1(arr1);//int[] arr2={1,1,2,2,2,3,3,3,4,4};int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };//System.out.println("预期结果："+2+" "+3);printOddTimesNum2(arr2);}

测试结果：

3.找到唯二出现奇数次的数字

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

解题思路：

  • 拿到最右侧的1：原数与相反数求与
  • 将数组中的数分为两组。分组依据：异或全数组的数据最右侧是否有1
  • 拿到最右侧为1的位置==》体现在一个二进制序列==》十进制数==》利用这个数判断数组中的数这一位是否有1，有则异或到一个ero1，得到其中一个结果
  • 另一个结果通过异或过整组数的ero和ero1再异或可得到

核心代码：

//arr中，有两种数出现奇数次public static void printOddTimesNum2(int[] arr){int ero=0;for (int cur:arr) {ero^=cur;}//提取出最右侧的1:原数与相反数相与int rightestOne=ero&(-ero);//System.out.println(rightestOne);//ero':提取出最右侧为这个1的一组数的结果int ero1=0;for (int cur:arr) {ero1^=(cur&rightestOne)==0" />0:cur;}ero=ero^ero1;System.out.println("出现奇数次的数字分别是："+ero+" "+ero1);}

4.找出唯一出现K次的数字

题意：一个数组中有一种数出现K次，其他数都出现了M次，已知M > 1，K < M，找到出现了K次的数，要求额外空间复杂度O(1)，时间复杂度O(N)

解题思路：

  • 说明：1.辅助数组为定长数组长度，空间复杂度为O（1）2.判断最右侧是不是(num>>i)&1，结果为1/0;提取最右侧的1：num&(-num)，结果为2的整数次幂
  • 使用辅助数组统计本数组中有多少个数字第i个二进制位上为1——统计方法：得到每个元素的2进制序列，将1出现的情况加到统计数组中
  • 使用ans变量，遍历这个数组如果这个位置1出现的次数对m取模若为k，说明目标数字这一位上有这个1，把它搞进结果变量中——或的手段
  • 取模m可取的前提是k<m。否则可能存在km的存在倍数关系。

对数器：

  • 使用map的方式

  • 查找次数为k的数值遍历表的方法——keySet（key）或者entrySet（ky和value的关系）

    对数器使用的keySet，这里对entrySet的使用做演示：

Set<Map.Entry<String, String>> entryseSet=map.entrySet(); for (Map.Entry<String, String> entry:entryseSet) { System.out.println(entry.getKey()+","+entry.getValue()); }//即通过getKey（）得到K，getValue得到V
  • 打乱顺序（shuffleOrder）：i位置数和随机生成的j(0~N-1)位置数进行交换

核心代码：

public static int km(int[] arr,int k,int m){int[] help=new int[32];//统计for (int cur:arr) {for (int i = 0; i < 32; i++) {help[i]+=(cur>>i)&1;}}//判断出现k次数的数中1出现的位置，并将相关状况放在ans的二进制序列中int ans=0;for (int i = 0; i < 32; i++) {ans|=help[i]%m==0" />0:1<<i;}return ans;}

测试代码：

//for testpublic static int test(int[] arr,int k,int m){HashMap<Integer,Integer> map=new HashMap<>();for (int i = 0; i < arr.length; i++) {if(map.containsKey(arr[i])){map.put(arr[i],map.get(arr[i])+1);}else{map.put(arr[i],1);}}int ans=0;for (int num:map.keySet()) {if(map.get(num)==k){ans=num;break;}}return ans;}//for testpublic static int[] generateRandomArray(int maxKinds,int range,int k,int m){int kNum=(int) (Math.random()*(range+1))-(int) (Math.random()*(range+1));int kinds= (int) (Math.random()*maxKinds)+2;//2~maxkinds+1//System.out.println("kinds:"+kinds);int[] arr=new int[k+(kinds-1)*m];//生成km的随机函数没写对....//int[] arr= new int[0];//try {//arr = new int[k+(kinds-1)*m];//} catch (NegativeArraySizeException e) {//System.out.println("k:"+k);//System.out.println("kinds:"+kinds);//System.out.println("m:"+m);k:2kinds:0m:4//throw new RuntimeException(e);//}int index=0;for(;index<k;index++){arr[index]=kNum;}kinds--;HashSet<Integer> set=new HashSet<>();set.add(kNum);while(kinds--!=0){int curNum=0;do {curNum=(int) (Math.random()*(range+1))-(int) (Math.random()*(range+1));}while(set.contains(curNum));set.add(curNum);for (int i = 0; i < m; i++) {arr[index++]=curNum;}}shuffleOrder(arr);return arr;}//for test//打乱数组顺序:public static void shuffleOrder(int[] arr){for (int i = 0; i < arr.length; i++) {int j= (int) (Math.random()*arr.length);int tmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}}//for testpublic static void main(String[] args) {boolean succeed=true;int kinds=5;int range=30;int maxTimes=9;int testTimes=1000;for (int i = 0; i < testTimes; i++) {int a = (int) (Math.random() * maxTimes) + 1; // a 1 ~ 9int b = (int) (Math.random() * maxTimes) + 1; // b 1 ~ 9int k = Math.min(a, b);int m = Math.max(a, b);// k < mif (k == m) {m++;}int[] arr=generateRandomArray(kinds,range,k,m);int ret1=km(arr,k,m);int ret2=test(arr,k,m);if(ret1!=ret2){System.out.println("k="+k+"m="+m);System.out.println("km:"+ret1);System.out.println("test:"+ret2);System.out.println(Arrays.toString(arr));System.out.println("Oops!Error!");succeed=false;break;}}if(succeed){System.out.println("succeed!");}}

测试结果：

位运算之异或运算题目总结

定义：

相同为0，相异为1。

理解：无进位相加

性质：

  • 0^N=N
  • N^N=0
  • 满足交换律和结合律

例题总结：

  • 不使用临时变量交换：三个等式aba
  • 寻找偶数次中的唯一奇数次：全部异或
  • 寻找偶数次中的唯二奇数次：异或分组异或；分组规则最右侧的1（相反数的补）
  • 寻找M次中的K次：辅助数组；对每个二进制统计（移位）；对辅助数组遍历（或）