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

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

巧用二进制 + int 数组

执行用时：7 ms, 在所有 Java 提交中击败了66.18% 的用户 内存消耗：39.5 MB, 在所有 Java 提交中击败了40.31% 的用户

class Solution {
    /**
     * 以用例 {3, 4, 3, 3} 为例子
     *
     * 把 nums 内的整数拆分为二进制累加到 bits 数组中
     * 3 的二进制：011
     * 4 的二进制：100
     * 累加之后 bits 结果：[..., 1, 3, 3]
     *
     * 再将 bits 内的元素对 3 取余后转换为十进制
     */
    public int singleNumber(int[] nums) {
        int[] bits = new int[32];
        // 把 nums 内的整数拆分为二进制累加到 bits 数组中
        for (int num : nums) {
            for (int i = 31; i >= 0; i--) {
                if (num != 0) {
                    bits[i] += (num & 1);
                    num >>= 1;
                }
            }
        }
        // 将二进制转为十进制
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res += bits[i] % 3;
        }
        return res;
    }
}