本文共 3424 字，大约阅读时间需要 11 分钟。

题目描述

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

分析

如果题目对空间复杂度没有太高的要求，可以参考之前的问题，。对数组遍历一次，用LinkedHashMap存放每个数字出现的次数，对LinkedHashMap遍历，可以方便地找出出现次数为1次的两个数字。

牛客AC：

//num1,num2分别为长度为1的数组。传出参数//将num1[0],num2[0]设置为返回结果import java.util.Map;import java.util.LinkedHashMap;import java.util.Map.Entry;public class Solution {
       public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {        if(array == null || array.length <= 1)            return;        Map
   
     map = new LinkedHashMap
    
     ();        for(int i = 0; i < array.length; i++) {            int tmpNum = array[i];            if(map.containsKey(tmpNum)) {                int count = map.get(tmpNum) + 1;                map.remove(tmpNum);                map.put(tmpNum, count);            } else {                map.put(tmpNum, 1);            }        }        int flag =0;        int[] nums = new int[2];        for(Entry
     
       entry : map.entrySet()) {            if(entry.getValue() == 1) {                nums[flag] = entry.getKey();                flag++;            }        }        num1[0] = nums[0];        num2[0] = nums[1];    }}
     
    
   

剑指offer原题描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是$O(n)$，空间复杂度是$O(1)$。

分析

使用Map容器存储数字次数的方法，时间复杂度为$O(n)$，空间复杂度是$O(n)$，由于空间复杂度是$O(1)的要求，本题不能直接使用Map容器的方法。

推荐解法

首先考虑这个数组中只有一个数字出现一次的情况：异或运算的性质是任何一个数字异或运算它自己都等于0。如果只存在一个这样只出现一次的数字，在该数组中从头到尾依次异或运算每一个而数字，成对出现两次的数字就被异或运算抵消了，最后剩下的就是只出现一次的数字。

再考虑题目中有两个数字出现一次的情况：如果可以把原数组拆分成两个子数组，并且每个子数组都只包含一个这样的数字，就可以通过异或运算分别得到这两个数字。

如果从头到尾一次异或运算数组中的每一个数字，由于有两个（num1,num2)只出现一次的情况，那些两两成对出现的数字被异或运算抵消后，最后的结果(resultExclusiveOR)一定是那两个数字异或运算的结果。因为这两个数字肯定不一样，则resultExclusiveOR的二进制表示中至少有一个bit位为1（说明num1,num2在该bit位上肯定是不同的，异或运算的结果才可能是1）。找到resultExclusiveOR中第一个1所在的bit位，记为indexBitOf1，对于原数组中的每一个数字，如果对应的indexBitOf1的bit位上也为1，则同分在一个子数组；其他的数字分在另一个子数组。则出现了两次的数字肯定被分配在同一个子数组，因为两个相同的数字任意一位都是相同的。由于两个不同的只出现一次的数字也被分配在了不同的子数组，因此对每一个子数组进行两两异或运算，最后得到的结果就是两个不同的只出现一次的数字。

牛客AC：

/**     * //num1,num2分别为长度为1的数组。传出参数     * //将num1[0],num2[0]设置为返回结果     * @param array     * @param num1     * @param num2     */    public void FindNumsAppearOnce(int[] array,int[] num1, int[] num2) {        if(array == null || array.length <2)            return;        int resExclusiveOR = 0; // 保存异或运算的结果        int length = array.length;        for(int i = 0; i < length; i++) // 进行两两异或运算            resExclusiveOR ^= array[i];        // 获取1所在的bit位索引        int indexBitOf1 = getFirstIndexOfBit1(resExclusiveOR);        // 利用异或运算查找只出现一次的数字        for(int i = 0; i < length; i++) {            int num = array[i];            // 根据数字的indexBitOf1的bit位上是否是1，划分为两个子数组            // 则两个不同的只出现一次的数字分别位于不同的子数组            // 在子数组中两两异或运算即得到只出现一次的数字            if(isIndexBit1(num, indexBitOf1))                   num1[0] ^= num;            else                num2[0] ^= num;        }    }    // 获取二进制表示中1第一次出现的bit位索引    public int getFirstIndexOfBit1(int num) {        int indexBitOf1 = 0;        // 循环条件为数字和1进行与运算的结果等于0        // 并且bit为小于int类型的bit位数（4个字节，32位），具体和虚拟机的实现有关        while((num & 1) == 0 && indexBitOf1 < Integer.SIZE) {            num = num >> 1;        indexBitOf1++;        }        return indexBitOf1;    }    // 判断数字num的二进制表示中的第indexBitOf1的bit位上是否是1    public boolean isIndexBit1(int num, int indexBitOf1) {        num = num >> indexBitOf1;        if((num & 1) == 1)            return true;        else            return false;    }

参考

转载地址：http://lzxgi.baihongyu.com/