每日一练Day04：寻找单身狗

你的名字 2024-04-01 15:55 74阅读 0赞

#### 寻找单身狗 ####

*  一、一个单身狗
 *  二、两个单身狗

--------------------

寻找单身狗实际上是力扣上的《只出现一次的数字》具体描述如下：

## 一、一个单身狗 ##

![76539cfcb250467c99c287972ca65897.png][]

**本题的特点是：** 非空数组、其余数字出现两次、寻找只出现一次的数字。那么如何寻找那个”单身狗“呢？

**思路：**  
我们已学过异或操作符`^`,异或的特点是，对应二进制位相同为`0`，相异为`1`。了解这样的原理就可以很容易得到，如果对应两个相同的数字，异或结果必为0，0和非零数字异或为非零数字。已知这种原理后，如果我们将数组中的所有元素异或，出现两次的的元素将异或为0，0与“单身狗”异或恰能得到所求“单身狗”。

**理论成立，实践开始：**

public static int singleNumber(int[] array) {
        
            int num=0;
            for (int i = 0; i < array.length ; i++) {
        
                num^=array[i];
            }
            return num;
        }

**测试结果：**

![c49838d30b894c1da6799a1d3cf27ce1.png][]

--------------------

## 二、两个单身狗 ##

本题可以说是上一题的进阶版本，难度也由简单——>中等。

![7a9e298644244f0685ed3f561265c154.png][]

**题目特点：**非空数组、其余数字都出现了两次、寻找两个只出现一次的数字。

**思路：**  
对于这道题如果我们还是将所有元素异或，显然是得不到答案的。那么应该怎么做呢？解决这道问题用到了数字的分组，如果我们将存在的两个“单身狗“分别分到不同的两组中，剩下的两两相同的数字分别分到两边，依旧是异或的原理，将两组数字分别异或，最后得到的两个异或结果不就是最终答案吗？

当然，说的简单，我们该怎样分组呢？这里提供了这样一种思路：

> 1、首先我们先将所以的数字异或，由于仅有两个“单身狗”，其余数字均出现两次，这样得到的结果就相当于是两个”单身狗“异或的结果。  
>   
> 2、由于我们的目的很明确，就是将两个”单身狗“分别分到两个组中，其余两两相同的数字放到它们两边即可。所以我们可以找到异或后二进制为1的位，因为二进制为1说明这是两个”单身狗“数字不同的二进制位，以此二进制位进行分组就可以将两个”单身狗“数字分别放到不同的组中，同时会将其余两两相同的数字分到他们两边，最后分别异或即可得到结果。

可能文字描述不够直观，下面以nums = \[1,2,1,3,2,5\]为例，**画图讲解：**

![在这里插入图片描述][1df6d6eb83ab4b5eb1d6c8f4cfb3b380.png]

**理论成立，实践开始：**

public static int[] sigleNumbers(int[] array) {
        
            int[] nums=new int[2];
            int tmp=0;
            int i=0;
            
            //整体异或
            for (i = 0; i < array.length; i++) {
        
                tmp^=array[i];
            }
            
            //寻找二进制位为1的位，用于分组
            for (i=0;i<32;i++) {
        
                if(((tmp>>>i)&1)==1) {
        
                    break;
                }
            }
            
            int num1=0;
            int num2=0;
            //分组异或
            for (int j = 0; j < array.length; j++) {
        
                if(((array[j]>>>i)&1)==1) {
        
                    num1^=array[j];
                } else {
        
                    num2^=array[j];
                }
            }
            nums[0]=num1;
            nums[1]=num2;
            return nums;
        }

**测试结果：**

![dd05f77976f948c3ac15c2aa1adf9f22.png][]

\------------------ （本章完）------------------

[76539cfcb250467c99c287972ca65897.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8fce736166aa4a47b4c64cdf81d2de99.png
[c49838d30b894c1da6799a1d3cf27ce1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/42a00ff2ff274b57a6ca81380f0b8a26.png
[7a9e298644244f0685ed3f561265c154.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5021aa1fdad745a894817f84a295cc87.png
[1df6d6eb83ab4b5eb1d6c8f4cfb3b380.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/dea1ecfe68eb4e73bfc84bf0e9e18e41.png
[dd05f77976f948c3ac15c2aa1adf9f22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c7b0d23c566045c19b1ebad1d288021a.png