8月算法训练------第十二天（位运算）解题报告

题目类型：位运算
题目难度：中等

第一题、剑指 Offer 56 - I. 数组中数字出现的次数

1. 题目链接：剑指 Offer 56 - I. 数组中数字出现的次数
2. 思路分析：
   这一题运用位运算，十分巧妙，我们知道异或运算的规则是将相同的两个数异或为1，不同的数异或为0。
   所以当两个相同的数异或之后，他们的结果为0。
   当数组中有一个不成对的数字时，其余的数都异或为0，最后的结果就是这个数。
   但这一题中有两个不同的数，将其中所有的数都异或之后结果一定是两个不同数异或的结果相等（因为其余相同的数异或之后结果都为0），但我们应如何从异或结果找到这两个原始数呢？
   那就要将其拆分当遇到某一位数字与1进行与运算结果不为0时，说明两个数的这一位数的值肯定不同，我们需要从低到高找到这一个不同数的最低位，这是将两个数分开的关键。
   找到最低位后，需要重新遍历一遍数组当数组中的数与这一位进行与运算，当结果为1，就与x进行异或；当结果为0，就与y进行异或。就是说将这个数组分成两个子数组，这两个子数组中都有一个是单独出现，将这两个子数组进行异或就能得到只出现一次的值了。
3. 代码：

class Solution {
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums){
            n ^= num;
        }
        while((n & m) == 0){
            m <<= 1;
        }
        for(int i : nums){
            if((m & i) != 0){
                x ^= i;
            } else{
                y ^= i;
            }
        }
        return new int[]{x, y};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第二题、剑指 Offer 56 - II. 数组中数字出现的次数 II

1. 题目链接：剑指 Offer 56 - II. 数组中数字出现的次数 II
2. 思路分析：
   相信这一题大家最能想到的就是用哈希表做，将所有数存入一个hashMap中，遍历这个hashMap，当值为1时，就返回键，就是结果。
3. 代码：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        for(int num : nums){
            if(map.containsKey(num)){
                int n = map.get(num);
                map.replace(num, n, n+1);
            }else{
                map.put(num, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if((Integer)entry.getValue() == 1){
                return (Integer)entry.getKey();
            }
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19