【剑指Offer】040——数组中只出现一次的数字 （数组）

题目描述

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

解题思路

法一：大家都能想到的HashMap法
法二：异或法

任何一个数字异或它自己都等于0。

如果数组中一个数字是只出现一次的，其他数字都是成双成对出现的，那么我们从头到尾依次异或数组中的每个数字，最终的结果刚好就是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。

那么回到我们的题目，因为有两个只出现一次的数字，所以我们可以试着把原数组分成两个子数组，使得每个数组包含一个只出现一次的数字，而其他数字都成对出现两次。如果这样拆分成两个数组，那么我们就可以按照之前的办法分别对两个数组进行异或运算找出两个只出现一次的数字。

问题来了，如何进行分组呢？
我们还是从头到尾依次异或数组中的每个数字，那么最终得到的结果就是两个只出现一次的数字异或的结果。由于这两个数字不一样，所以异或的结果至少有一位为1，我们在结果数字中找到第一个为1的位置，记为index位，现在我们以第index位是不是1为标准把原数组拆分成两个子数组，第一个子数组中的数组第index位都为1，第二个子数组中的数组第index位都为0，那么只出现一次的数字将被分配到两个子数组中去，于是每个子数组中只包含一个出现一次的数字，而其他数字都出现两次。这样我们就可以用之前的方法找到数组中只出现一次的数字了。

参考代码

Java

import java.util.HashMap;
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    // 方法一 hashmap法
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>();
        for (int i = 0; i < array.length; i++) {
            if (temp.containsKey(array[i])) temp.remove(array[i]); // 存在了，再次出现就移除
            else temp.put(array[i], 1);
        }
        int[] a = new int[array.length];
        int i = 0;
        for (Integer k: temp.keySet()) {
            a[i] = k;
            i ++;
        }
        num1[0] = a[0];
        num2[0] = a[1];
    }
    // 方法二 异或法
    public void FindNumsAppearOnce2(int [] array,int num1[] , int num2[]) {
        num1[0] = 0;
        num2[0] = 0;
        if (array.length == 0) return;
        int num = 0; // 最终结果是数组中只出现一次的整数之间的异或
        // 利用a^b^c=a^(b^c)=(a^c)^b；0与一个数字异或结果还为这个数字
        for (int i = 0; i < array.length; i++) num ^= array[i]; // 数组中每个数字进行依次进行异或
        // 查找
        int index = 0; // 一个二进制整数用8位表示
        // 直到
        while ((num & 1) == 0 && index < 8 ){
            num = num >> 1;   // 相当于截取num二进制中最后1位二进制位的结果
            index ++;
        }
        for (int i = 0; i < array.length; i++) {
            if (isa1(array[i],index)) num1[0] ^= array[i];
            else num2[0] ^= array[i];
        }

    }
    public boolean isa1(int i, int index){
        i = i>>index;
        return (i&1) == 1;
    }
}

Python

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        res = {}
        for i in range(len(array)):
            if str(array[i]) in res.keys():
                del res[str(array[i])]
            else:
                res[str(array[i])] = 1
        res_list = []
        for key in res.keys():
            res_list.append(key)
        return res_list

个人订阅号

image