剑指 Offer 56 - II. 数组中数字出现的次数 II

剑指 Offer 56 - II. 数组中数字出现的次数 II

• 解题思路
• 代码

解题思路

如果数组中的数字除一个只出现一次之外,其他数字都出现了两次。我们可以如Solution56_1一样用异或位运算(^)解决这个问题。

上述思路不能解决这里的问题,因为三个相同的数字的异或结果还是该数字。尽管我们这里不能应用异或运算,我们还是可以沿用位运算的思路。
如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的二进制表示中对应的那一位是0;否则就是1;

实际上，只需要修改求余数值 m ，即可实现解决 除了一个数字以外，其余数字都出现 m 次 的通用问题。

这种解法的时间效率是O(n)。我们需要一个长度为32的辅助数组存储二进制表示的每一位的和。由于数组的长度是固定的,因此空间效率是O(1)。

代码

class Solution {
        public int singleNumber(int[] nums) {
        if (nums.length == 0) {
            return -1;
        }
        //java int类型有32位，其中首位为符号位：用于记录 数组中所有数字 的 每一位的和
        int[] bitSum = new int[32];
        int res = 0;

        for (int num : nums) {
            //二进制数为0001，方便确定num的哪一位是1，要放在这里，每次循环开始都要初始化
            int curBit = 1;
            /*
                由高到低，遍历当前数字的每一位，
                若 当前位为1，则使bitSumArray数组的相应的单元的值+1
            */
            for (int i = 31; i >= 0; i--) {
                if ((curBit & num) != 0) {
                    bitSum[i] = bitSum[i] + 1;
                }
                curBit <<= 1;
            }
        }
        /*遍历bitSum数组的每一位，取每一位和3取余的结果（肯定为0或1）
        并将其 加入到 结果result的适当位上*/
        for (int i = 0; i < 32; i++) {
            res = res << 1;
            res = res + bitSum[i] % 3;//这两步顺序不能变，否则最后一步会多左移一次
        }

        return res;
    }
}