/*

• 已知数组中其他数都出现了N次，只有一种数出现了K次
• 怎么找到出现了K次的数？做到时间复杂度O(N)，额外空间复杂度O(1)
• 规定：N > 1，K > 0，K < N
• 
  

• */

  

  二进制

  

• 搞一个数组，

• (每位 % N) / k

举例子

public class _补充题_KN {
    // 右额外空间复杂度
    public static int get1(int[] arr, int k, int n) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) == k) {
                return key;
            }
        }
        return -1;
    }
    // 时间复杂度O(N)，额外空间复杂度O(1)
    public static int get2(int[] arr, int k, int n) {
        int[] count = new int[32];
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                if ((num & (1 << i)) != 0) {
                    count[i]++;
                }
            }
        }
        for (int i = 0; i < count.length; i++) {
            count[i] = (count[i] % n) / k;
        }
        int ans = 0;
        for (int i = 0; i < count.length; i++) {
            ans |= count[i] << i;
        }
        return ans;
    }
}