算法|2.异或运算

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

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

解题思路：

使用异或运算的性质

在这里插入图片描述

代码及运行结果：

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kkTo46xE-1685088032675)(F:\typora插图\image-20230526125538881.png)]$

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

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

解题思路：

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

核心代码：

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

测试方法：

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

//for test
public 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);}

测试结果：

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aOPZG8a5-1685088032675)(F:\typora插图\image-20230526140344898.png)]$

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:2
            kinds:0
            m: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!");}}