一、题目

剑指 Offer 56 - II. 数组中数字出现的次数 II(位运算的妙用)

  1. 题目描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例1：

1
2
输入：nums = [3,4,3,3]
输出：4

示例2：

1
2
输入：nums = [9,1,7,9,7,9,7]
输出：1

二、分析

方法1：hashMap统计个数，遍历返回

比较常规的思路就是通过hashMap统计个数，然后遍历返回即可。思路简单，但这种方法显示没有充分利用题中的条件其他数字都出现了三次。所以一定不是最优解。

方法2：位运算

分析

其他数字出现了三次，这是我们解题的突破点。

做这种数字题，我们要有位运算的思想在，所以我们绞尽脑汁往位运算那边去靠。我们试想一下，如果将所有数字转换为二进制，然后观察一下会有什么规律呢？如下：

1
2
3
4
5
6
7
8
9
10
nums=[4,4,4,5,5,5,3]
出现3次：4,5
*          4:0100b
*          4:0100b
*          4:0100b
*          5:0101b
*          5:0101b
*          5:0101b
出现1次：3
*          3:0011b

我们发现4,5这两个重复的数字每一位之和必定是3的倍数，道理很简单，因为相同的数字出现了3次，多个相同的数之和肯定是3的倍数。

利用这个规律，每位和是三的倍数，我们将所有数字每位求和，然后模3，就是出现一次数字的对应位。如下：

1
2
3
4
5
6
7
8
9
10
11
nums=[4,4,4,5,5,5,3]
出现3次：4,5
*          4:0100b
*          4:0100b
*          4:0100b
*          5:0101b
*          5:0101b
*          5:0101b
*          3:0011b
每位进行sum%3结果就是要求的数，如下：
*          3:0011b

复杂度

时间O(N)

两次遍历O(32)*O(N)

空间O(1)

常数辅助遍历O(1)

三、代码

方法1：hashMap统计个数，遍历返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    /**
     * 题目：剑指 Offer 56 - II. 数组中数字出现的次数 II
     * 描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字
     * 方法：哈希表存储
     * 复杂度：时间O(N):两次遍历数组O(2*n)
     *        空间O(N):线性哈希表O(N)，和常数辅助遍历j,i,O(1)
     */

    public static int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int j=0;
        for (int i : nums) {
//            j=hashMap.get(i)==null?1:hashMap.get(i)+1;//可以优化，因为我们只要计数为1的key,超过1的key我们可以直接设置为-1。减少get操作。
            j=hashMap.get(i)==null?1:-1;//优化减少get操作。

            hashMap.put(i,j);

        }
        for (Integer i : hashMap.keySet()) {
            if (hashMap.get(i)==1) return i;
        }
        return -1;
    }


方法1小优化，避免计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * 题目：剑指 Offer 56 - II. 数组中数字出现的次数 II
 * 描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字
 * 方法：哈希表存储,上面方法优化。将hashMap分为符合条件的和不符合条件的，减少计数
 * 复杂度：时间O(N):两次遍历数组O(2*n)
 *        空间O(N):线性哈希表O(N)
 */

public static int singleNumberB(int[] nums) {
    HashMap<Integer, Boolean> hashMap = new HashMap<>();
    for (int i : nums) {
        hashMap.put(i,hashMap.containsKey(i));

    }
    for (Integer i : hashMap.keySet()) {
        if (hashMap.get(i)==false) return i;
    }
    return -1;
}

方法2：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 题目：剑指 Offer 56 - II. 数组中数字出现的次数 II
 * 描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字
 * 方法：位运算如下
 *          4:0100b
 *          4:0100b
 *          4:0100b
 *          3:0011b
 *        sum:0011(每位求和模3就是结果，可以拓展到其他数字出现了n次)
 *
 * 复杂度：时间O(N):两次遍历O(32)*O(N)
 *        空间O(1):常数辅助遍历O(1)
 */

public static int singleNumberA(int[] nums) {
    int sum;//所有数字某个位置之和
    int res=0;//结果
    for (int j = 0; j <32; j++) {
        sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum += ( (nums[i] >> j) & 1);//用"&1" 和每位测试是1或0
        }
        res +=( (sum%3) << j);
    }
    return res;

}


四、总结

这道题用位运算可以拓展到其他数字重复n次，具有一定的通解性。本质上利用转换为二进制之后，通过取余运算，找到独一无二的数。

位运算常见性质总结:

1
2
3
4
5
6
7
0 or 任何数等于其本身
0 xor 任何数等于其本身（本题用到性质）
1 and 任何数等于其本身（本题用到性质）

0 and 任何数等于0
1 or 任何数等于1
1 xor 任何数等于本身取反