牛客网算法——名企面试的笔试（5）

package 牛客网名企面试笔试问题2021;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Classname 返回出现的1次的数字
 * @Description TODO
 * @Date 2021/3/9 9:57
 * @Created by xjl
 */
public class 返回出现的1次的数字 {
    /**
     * @description TODO
     * 出现k次就不能再用异或的方法了，因为k(奇数)个相同的数异或还是得到本身。但是还是可以采用位运算的思想，
     * 因为出现k(奇数)次的数字每个位（0或者1）也是出现k(奇数)次，因此可以每一位的和能够被k整除（对k取余为0）。
     * 所以如果把每个数的二进制表示的每一位加起来，对于每一位的和，如果能被k整除，那对应那个只出现一次的数字的那一位就是0，否则对应的那一位是1。
     *
     * 我们需要用一个长度为32（int型二进制表示最多为32位，4字节）的数组bitSum保存每一位的和
     * 具体来讲实现过程是，先初始化为0，然后对于每个数字，遍历它二进制表示的每一位，如果这一位是1，bitSum对应的那一位就加1。
      * @param: arr
     * @param: k
     * @date: 2021/3/9 10:22
     * @return: int
     * @author: xjl
    */
    public int foundOnceNumber3 (int[] arr, int k) {
        // 每个二进制位求和，如果某个二进制位不能被k整除，那么只出现一次的那个数字在这个二进制位上为1。
        int[] binarySum = new int[32];
        for(int i = 0; i< 32; i++){//求每个二进制位的和
            int sum = 0;
            for(int num : arr){
                sum += (num >>i & 1);//依次右移num，同1相与，计算每一位上1的个数
            }
            binarySum[i] = sum;
        }
        int res = 0;
        for (int i = 0; i< 32; i++){
            if(binarySum[i]%k!=0){
                res += 1