算法|2.异或运算

今天药忘吃喽~ 2024-03-16 09:20 49阅读 0赞

## 算法|2.异或运算 ##

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

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

解题思路：

*  使用异或运算的性质

![在这里插入图片描述][421196d2b66444db9c0b55304bc1e3fc.jpeg_pic_center]

代码及运行结果：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kkTo46xE-1685088032675)(F:\\typora插图\\image-20230526125538881.png)\]][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)\]][img-aOPZG8a5-1685088032675_F_typora_image-20230526140344898.png]

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

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

解题思路：

![在这里插入图片描述][f0aa2cdae2254f07b2623c52cf0401d2.jpeg_pic_center]

*  **拿到最右侧的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)

解题思路：

![在这里插入图片描述][032ee070c5354348843734bf36001691.jpeg_pic_center]

*  说明：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 test
        public 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 test
        public 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 test
        public 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 ~ 9
                int b = (int) (Math.random() * maxTimes) + 1; // b 1 ~ 9
                int k = Math.min(a, b);
                int m = Math.max(a, b);
                // k < m
                if (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!");
            }
        }

测试结果：

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

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

**定义：**

相同为0，相异为1。

理解：无进位相加

**性质：**

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

**例题总结：**

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

[421196d2b66444db9c0b55304bc1e3fc.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/d7fc5b0bb3814caaa56e074eae45ff52.png
[img-kkTo46xE-1685088032675_F_typora_image-20230526125538881.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/b69a43f2d83c46309ec30c4110e2b78a.png
[img-aOPZG8a5-1685088032675_F_typora_image-20230526140344898.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e5e3ae16b51d4cafae24adc235f4171e.png
[f0aa2cdae2254f07b2623c52cf0401d2.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/fe087c23a8fc4f5e9cb868d53697a1a7.png
[032ee070c5354348843734bf36001691.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9b0b1918cbbe46a39403f7ca9ecef1bd.png
[img-anDCEMKM-1685088032677_F_typora_image-20230526153038004.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6b37059a65a84f2db072d65399f89516.png