数组中数字出现的次数

记录Leetcode上的一道题目，欢迎交流，指正错误。

1. 普通版

LeetCode链接

题目：

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

示例 1：

输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]

示例 2：

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

限制：

2 <= nums.length <= 10000

解题思路：

如果不考虑空间复杂度的话，可以考虑用map来完成，数组中的数字为key，出现的次数为value。要求时间复杂度为O(n)，空间复杂度为O(1)。

我们知道：两个相同的数字进行异或运算结果为0，任何数字与0异或运算结果为数字本身。若数组中只有一个数字只出现一次的话，则将所有数字直接异或运算，就能得到只出现一次的数字。现在数组中有两个只出现了一次的数字，则可以考虑将数组分成2块，让每一块中保证只有一个数字出现一次。

接下来只需考虑如何将数组分成2块:

• 重复的数字进行分组，很简单，只需要有一个统一的规则，就可以把相同的数字分到同一组了。例如：奇偶分组。因为重复的数字，数值都是一样的，所以一定会分到同一组！
• 两个不同数字的分组，假设为数字a，b。若我们将所有数字进行异或运算，得到数字k，则得到的k应该为数字a与b的异或结果。因为相同的数字异或结果为0，而任何数与0异或的结果为自身。对于数字k的二进制来说，若二进制中第一位数字1，则表示数字a和b的二进制中第一位不同（因为0与1异或为1，0与0异或为 0，1与1异或为0）。因此只要找到k的二进制数种任意一位为1，即可将a和b进行区分。

代码：

 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

class Solution {
    public int[] singleNumbers(int[] nums) {
        //用于将所有的数异或起来
        int k = 0;
        for(int num: nums) {
            k ^= num;
        }
        //这里 从最低位开始找k中的1
        int mask = 1;
        //(k & mask) == 1时表示已找到k中最低位的1，存于mask中，我们假设在index这个位为1
        while((k & mask) == 0) {
            mask <<= 1;
        }
        int a = 0;
        int b = 0;
 		//这里 让index位为0的数字和a分到一组，index位为1的分为一组（这里没有采用奇偶分组）
        for(int num: nums) {
            if((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

2. 进阶版

LeetCode链接

题目：

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

示例 1：

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

示例 2：

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

限制：

1 <= nums.length <= 10000 1 <= nums[i] < 2^31

解题思路（源于剑指Offer）：

这次是只有一个数字只出现了一次，但其他数字却出现了3次，因此也不能直接把所有数字进行异或运算，从而求出不一样的数字。如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次，则把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1;

上述思路同样适用于数组中一个数字出现一次，其他数字出现奇数次问题(如果是偶数次，直接用异或就可)。

代码：

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

class Solution {
    public int singleNumber(int[] nums) {
        //在java语言中，一个int数字4字节，32位。
        //sums 统计结果
        int[] sums = new int[32];
        int result = 0;
        for(int i = 0; i < 32; i++){
            int mask = 1 << i;
            for(int j = 0; j < nums.length; j++){
                //(mask & nums[j]) == mask 表示nums[j]的二进制中第i位为1
                if((mask & nums[j]) == mask) sums[i] += 1;
            }
            sums[i] %= 3;
            if(sums[i] == 1) result += mask;
        }
        return result;
    }
}

3. 小结

Java中的位运算：

• 与（&）运算：1 & 1 为 1; 1 & 0 为 0; 0 & 1 为 0； 0 & 0 为 0 。
• 或（|）运算：1 | 1 为 1; 1 | 0 为 1; 0 | 1 为 1； 0 | 0 为 0 。
• 非（~）运算：~ 1 为 0; ~ 0 为 1 。
• 异或（^）运算：1 ^ 1 为 0; 1 ^ 0 为 1; 0 ^ 1 为 1； 0 ^ 0 为 0 。

Java 可在整数类型（integral type）数据上进行位（bit）运算

整数类型：

• 字节型(byte，8 位)
• 短整型(short，16 位)
• 整型(int，32 位)
• 长整型(long，64 位)

Java中的移位运算：

• 左移运算符（<<）：丢弃最高位，0补最低位；4 << 2 为 16; -4 << 2 为 -16
• 右移运算符（>>）：符号位不变，左边补上符号位； 4 >> 2 为 1; -4 >> 2 为 -1
• 无符号右移运算符（>>>）：忽略了符号位扩展，0补最高位；

PS:无符号右移规则和右移运算是一样的，只是填充时不管左边的数字是正是负都用0来填充，无符号右移运算只针对负数计算，因为对于正数来说这种运算没有意义