NC156：数组中只出现一次的数（其它数出现k次）

解法1：排序

  public int foundOnceNumber(int[] arr, int k) {
        Arrays.sort(arr);
        for(int i = 0; i<arr.length-1; i++){
            if(arr[i]==arr[i+1]){
                i += k-1;
            }else{
                return arr[i];
            }

        }
        return arr[arr.length-1];
    }

解法2：位运算

出现k次就不能再用异或的方法了，因为k(奇数)个相同的数异或还是得到本身。但是还是可以采用位运算的思想，因为出现k(奇数)次的数字每个位（0或者1）也是出现k(奇数)次，因此可以每一位的和能够被k整除（对k取余为0）。所以如果把每个数的二进制表示的每一位加起来，对于每一位的和，如果能被k整除，那对应那个只出现一次的数字的那一位就是0，否则对应的那一位是1。

我们需要用一个长度为32（int型二进制表示最多为32位，4字节）的数组bitSum保存每一位的和
具体来讲实现过程是，先初始化为0，然后对于每个数字，遍历它二进制表示的每一位，如果这一位是1，bitSum对应的那一位就加1。

public int foundOnceNumber (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<<i;//左移恢复
            }
        }
        return res;
    }

解法3：HashMap

代码1：

public int foundOnceNumber (int[] arr, int k) {
        // write code here
        HashMap<Integer, Boolean> map = new HashMap<>();//key存数字，value表示是否出现过
        for(int num: arr){
            if(map.containsKey(num)){
                map.put(num, true);
            }else{
                map.put(num, false);
            }
        }
        Set<Integer> set = map.keySet();
        for(int num : set){
            if(map.get(num) == false){
                return num;
            }
        }
        return 0;
    }

代码2：

public int foundOnceNumber (int[] arr, int k) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();//key存数字，value表示是否出现过
        for(int num: arr){
            if(map.containsKey(num)){
                map.put(num, map.get(num)+1);
            }else{
                map.put(num, 1);
            }
        }
        Set<Integer> set = map.keySet();
        for(int num : set){
            if(map.get(num) == 1){
                return num;
            }
        }
        return 0;
    }