剑指offer40 数组中只出现一次的数字


剑指offer

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

题目描述

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

解法一:使用 map 存储

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.HashMap;
import java.util.Map;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {

        //1 使用 map 存储

        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){
                map.put(array[i],map.get(array[i])+1);
            }else{
                map.put(array[i],1);
            }
        }

        int cnt = 0;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){

            if(entry.getValue()==1 && cnt==0){
                num1[0] = entry.getKey();
                cnt++;
            }

            if(entry.getValue()==1 && cnt!=0){
                num2[0] = entry.getKey();
            }
        }
    }
}

解法二:异或运算

首先:位运算中异或的性质:两个相同数字异或=0,一个数和0异或还是它本身。

当只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。

首先还是先异或,剩下的数字肯定是A、B异或的结果,这个结果的二进制中的1,表现的是A和B的不同的位。我们就取最后一位1所在的位数,假设是第3位,接着把原数组分成两组,分组标准是第3位是否为1。

如此,相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数,肯定不在一组。然后把这两个组按照最开始的思路,依次异或,剩余的两个结果就是这两个只出现一次的数字。

        //2 异或
        /**
        首先:位运算中异或的性质:两个相同数字异或=0,一个数和0异或还是它本身。
        当只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。
        首先还是先异或,剩下的数字肯定是A、B异或的结果,这个结果的二进制中的1,表现的是A和B的不同的位。
        我们就取最后一位1所在的位数,假设是第3位,接着把原数组分成两组,分组标准是第3位是否为1。
        如此,相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数,肯定不在一组。
        然后把这两个组按照最开始的思路,依次异或,剩余的两个结果就是这两个只出现一次的数字。
        **/
        int temp = array[0];
        //首先把数组中的数字全部进行异或
        for (int i = 1; i < array.length; i ++){
            temp ^= array[i];
        }
        //把异或结果的最后一位1的那位找出来
        temp &= -temp;
        //以这一位是否为1或者0作为分类标准进行分类
        for (int val : array){
            if ((val&temp) == 0){
                num1[0] ^= val;
            } else {
                num2[0] ^= val;
            }
        }

文章作者: Hailong Gao
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Hailong Gao !
评论
  目录