转载

数组中只出现一次的数字

数组中只出现一次的数字

题目描述

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

思路

可以使用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;
    }
}
正文到此结束
本文目录