2021/4/30 数组中只出现一次的数（其它数出现k次）

题目描述

给定一个整型数组 arr 和一个整数 k(k>1)。
已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。
请返回只出现了 1 次的数。

示例

输入

[5,4,1,1,5,1,5],3
输出
4

解题思路

1. 将所有数字的二进制对应位置进行求和，用过 Excel 的胖友应该都知道求和操作，如图
   
   我们假设有四个数字，其中有三个重复的 2，和一个单独的 3；
2. 因为有 3 个数是重复的，所有把所有二进制位求和之后得到的数值进行取模操作，如图
   
   于是就得到了结果。

Java代码实现

public int foundOnceNumber (int[] arr, int k) {
        int[] count = new int[32];    // Java 中，int 有 32 位
        for (int i = 0; i < arr.length; ++i) {    // 将所有数的对应二进制位进行求和
            for (int j = 0; j < 32; ++j) {
                count[j] += arr[i] & 1;
                arr[i] >>>= 1;
            }
        }

        int res = 0;
        for (int i = 0; i < 32; ++i) {    // 求和之后再取出来，同时要取模操作
            res <<= 1;
            res |= count[31 - i] % k;    // 有 k 个相同的 1， 则 k % k == 0，剩下的就是多出来的那个数
        }


        return res;
    }