算法与数据结构

题目描述

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

实例

输入

[92,3,43,54,92,43,2,2,54,1]

输出

3,1

思路 & 解答

HashMap存储出现次数

使用hashmap存储数字出现的次数，key为出现的数字，value为该数字出现的次数。遍历里面所有的数字，如果hashmap中存在，那么value（次数）+1，如果hashmap中不存在,那么value置为1。

遍历完成之后，需要将次数为1的数字捞出来，同样是遍历hashmap，由于只有两个满足条件，我们设置一个标识变量，初始化为1，如果找到第一个满足条件的数字，除了写入放回数组中，还需要将该标识置为2，表示接下来找的是第2个。如果找到第2个，那么写入之后，直接return。

代码如下：

public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        Map<Integer, Integer> maps = new HashMap<>();
        if (array != null) {
            for (int n : array) {
                Integer num = maps.get(n);
                if (num == null) {
                    // map中不存在
                    maps.put(n, 1);
                } else {
                    // map中已经存在
                    maps.put(n, num + 1);
                }
            }
        }
        int index = 1;
        for (Map.Entry<Integer, Integer> entry : maps.entrySet()) {
            if (entry.getValue() == 1) {
                if (index == 1) {
                    num1[0] = entry.getKey();
                    index++;
                } else {
                    num2[0] = entry.getKey();
                    return;
                }
            }
        }
    }

C++ 代码如下：

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int> &array) {
        vector<int> res;
        // 创建一个哈希表
        set<int> mySet;
        for (int i = 0; i < array.size(); i++) {
            // 如果已经被当作key了，那就直接remove掉
            if (mySet.count(array[i]) > 0) {
                mySet.erase(array[i]);
            } else {
                // 否则就添加进去
                mySet.insert(array[i]);
            }
        }
        int i = 0;
        // 最后拿出来放进返回结果的数组中进行返回
        for (int num:mySet) {
            res.push_back(num);
        }
        return res;
    }
};

位运算

首先需要了解一定位运算知识，异或是指二进制中，一个位上的数如果相同结果就是0，不同则结果是0.也就是如果一个数的最低位是0，另一个数的最低位是0，那么异或结果的最低位是0；如果一个数的最低位是0，另一个数的最低位是1，那么异或结果的最低位是1。

异或操作可以交换，不影响结果：A^B^C = A^B^C
A^A=0,任何一个数异或自身，等于0，因为所有位都相同
A^0 = A，任何一个数异或0，等于自身，因为所有位如果和0不同，就是1，也就是保留了自身的数值

假设里面出现一次的两个元素为A和B，初始化异或结果res为0，遍历数组里面所有的数，都进行异或操作，则最后结果res = A^B。

但是我们拿到这个A和B异或之后的结果，怎么区分呢？

有一种巧妙的思路，因为A和B的某一位不同才会在结果中出现1，说明在那一位上，A和B中肯定有一个是0，有一个是1。

那我们取出异或结果res最低位的1，假设这个数值是temp（temp只有一个位是1，也就是A和B最后不同的位）

遍历数组中的元素，和temp进行与操作，如果和temp相与，不等于0。说明这个元素的该位上也是1。那就说明它很有可能就是A和B中的一个。

只是有可能，其他的数也有可能该位上为1。但是符合这种情况的，其他数肯定出现两次，而A和B只可能有一个符合，并且只有可能出现一次A或者B。

凡是符合和temp相与,结果不为0的，我们进行异或操作。也就是可能出现，res1 = B^C^D^C^D...^E^E^B或者res1 = A^C^D^C^D...^E^E。上面的式子可以视为res1 = B或者res1 = A

这样操作下来，我们就知道了res1肯定是其中一个只出现一次的数（A或者B）,而同时上面计算出了res = A^B,也就是可以通过res1^res求出另一个数。

代码如下：

    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        // A和B异或的结果
        int res = 0;
        for (int val : array) {
            res ^= val;
        }
        // temp保存了两个数最后一个不同的位
        int temp = res & (-res);
        // 保存和最后一个不同的位异或的结果
        int res1 = 0;
        for (int val : array) {
            // 不等于0说明可能是其中一个数，至少排除了另外一个数
            if ((temp & val) != 0) {
                res1 ^= val;
            }
        }
        // 由于其他满足条件的数字都出现两次，所以结果肯定就是只出现一次的数
        num1[0] = res1;
        // 求出另外一个数
        num2[0] = res ^ res1;
    }

C++ 代码如下：

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int> &array) {
        vector<int> results;
        // A和B异或的结果
        int res = 0;
        for (int val : array) {
            res ^= val;
        }
        // temp保存了两个数最后一个不同的位
        int temp = res & (-res);
        // 保存和最后一个不同的位异或的结果
        int res1 = 0;
        for (int val : array) {
            // 不等于0说明可能是其中一个数，至少排除了另外一个数
            if ((temp & val) != 0) {
                res1 ^= val;
            }
        }
        // 由于其他满足条件的数字都出现两次，所以结果肯定就是只出现一次的数

        int res2 = res ^res1;
        if (res1 < res2) {
            results.push_back(res1);
            results.push_back(res2);
        } else {
            results.push_back(res2);
            results.push_back(res1);
        }
        return results;
    }
};

今日感想： 位运算真的很强大！！！