NC156 数组中只出现一次的数（其它数出现k次）_对于给定的 n个数,其中有一个数 k只出现过一次,其他数

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

思路一：用hashMap存储每个数字出现的次数，最后遍历一下找出value出现一次的数字。
思路二：位运算
例子：arr={1,1,3,3,5},k=2; 那么转化为二进制 {1,1,11,11,101},统计每个二进制位上1的个数。
如果统计时不包含出现一次的那个数，那么一定是k的倍数，二进制最低位统计为5，倒数第二位统计为2，倒数第三位统计为1。如果统计时包含出现一次的那个数，会导致比k的倍数多出1。
int 类型为32位的二进制，用32大小的数组存放每位统计的结果。

import java.util.HashMap;

public class FoundOnceNumber {
    public static void main(String[] args) {
        int [] arr={1,3,7,1,3};
        int i = foundOnceNumber(arr, 2);
        System.out.println(i);
        int i2 = foundOnceNumber2(arr, 2);
        System.out.println(i2);

    }
    //hashMap法
    public static int foundOnceNumber (int[] arr, int k){
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])){
                map.put(arr[i],1 );
            }else {
                map.put(arr[i],map.get(arr[i])+1);
            }
        }
        for (Integer key :map.keySet()){
            if (map.get(key)==1){
                return key;
            }
        }
        return 0;
    }

//位运算法
    public static int foundOnceNumber2 (int[] arr, int k){
        int[] binarySum = new int[32];
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int num:arr){
                sum+=((num >>i) &1);
            }
            binarySum[i]=sum;
        }
        int ans=0;
        for (int i = 0; i < 32; i++) {
            if (binarySum[i]%k!=0){
                ans += 1<<i;
            }
        }
        return ans;
    }
}


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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51