数组中只出现一次的数字

﹏ヽ暗。殇╰゛Y 2023-06-30 08:39 20阅读 0赞

#### 数组中只出现一次的数字 ####

#### 题目描述 ####

> 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

#### 思路 ####

> 可以使用map数据结构解决问题,map的key是数字，value是其在数组中出现的次数。遍历一遍数组，
> 
> 初始化map，遍历一遍map，得到在数组中仅出现一次的两个数字。但是更巧妙的方法是使用**位运算**

#### 使用位运算的具体步骤如下 ####

##### 牢记两点，任何两个相同的数相异或，均为零。零与任何数异或均为其本身。 #####

以数组`[2,2,3,4,4,5,6,5]`为实例

*  数组里面所有数字相异或，得到数组中唯一出现一次的两个数相异或的结果。
    
        2^2^3^4^4^5^6^5 => 3 ^ 6 => 011 ^ 110 => 101
 *  数组中唯一出现一次的两个数异或的结果，二进制表示至少有一位为1。(**两个数不同，异或结果必有一位为1**)
    
    可以使用此性质，将数组分为两部分，一部分包含`只出现一次的一个数字`，一部分包含`另外一个只出现一次的数字`。
    
        3 ^ 6 => 011 ^ 110 => 101
        找到异或结果，第一次出现1的位置，倒数第一位 
        3=>011,倒数第一位为1  6=>110,倒数第二位为0
        按照倒数第二位是否为1，将数组分为两部分(3和6一定分在不同的部分)
        [3,5,5]  [2,2,4,4,6]
 *  最后对这两部分分别进行异或操作，分别得到只出现一次的一个数字。
    
        3^5^5 => 3
        2^2^4^4^6 => 6

#### 完整java代码 ####

//num1,num2分别为长度为1的数组。传出参数
    //将num1[0],num2[0]设置为返回结果
    public class Solution { 
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
            if(array == null || array.length < 2) return;
            
            int res = array[0];
            for(int i = 1;  i < array.length; i++) res = res ^ array[i];
            
            int base = 2;
            while(true) { 
                if(res % base == 0)  base *= 2;
                else break;
            }
            base = base / 2;
            
            boolean flag1 = false; boolean flag2 = false;
            int number1 = 0; int number2 = 0;
            
            for(int i = 0; i < array.length; i++) { 
                if((base & array[i]) != 0) { 
                    if(flag1 == false) { number1 = array[i]; flag1 = true;}
                    else number1 = number1 ^ array[i];
                } else { 
                    if(flag2 == false) { number2 = array[i]; flag2 = true;}
                    else number2 = number2 ^ array[i];
                }
            }
            
            num1[0] = number1; num2[0] = number2;
        }
    }