数组中某个数出现奇数次

一个数组中有一种数出现了奇数次，其他数出现了偶数次，怎么找到并打印这个数？ #

// arr中只有一种数，出现奇数次
public void printOddTimesNum(int[] arr) {
  int eor = 0;
  for (int i = 0; i < arr.length; i++) {
    eor ^= arr[i];
  }
  System.out.println(eor);
}

一个数组中有两种数出现了奇数次，其他数出现了偶数次，怎么找到并打印这个数？ #

public void printOddTimesNum(int[] arr) {
  int eor = 0;
  for (int i = 0; i < arr.length; i++) {
    eor ^= arr[i];
  }
  // 此时 eor=a^b (a!=b)
  int rightOne = eor & (-eor); // 提取出最右的1

  int onlyOne = 0;
  for (int i = 0 ; i < arr.length;i++) {
    if ((arr[i] & rightOne) != 0) { // arr[1] = 1111000111_1_0000; rightOne= 0000000000_1_0000 只有最右1的位置都一样 才为 true
      onlyOne ^= arr[i];
    }
  }
  // 此时 onlyOne = a；(eor ^ onlyOne) = b
  System.out.println(onlyOne + " " + (eor ^ onlyOne));
}

一个数组中有两种数出现了K次，其他数出现了M次，M>1，K<M，怎么找到并打印出现了K次的数？ 要求时间复杂度 O(n)，额外空间复杂度O(1) #

纯哈希表实现（额外空间复杂度不满足条件用于测试）

public int test(int[] arr, int k, int m) {
  HashMap<Integer, Integer> map = new HashMap<>();
  for (int num : arr) {
    if (map.containsKey(num)) {
      map.put(num, map.get(num) + 1);
    } else {
      map.put(num, 1);
    }
  }
  int ans = 0;
  for (int num : map.keySet()) {
    if (map.get(num) == k) {
      ans = num;
      break;
    }
  }
  return ans;
}

解法一：

public HashMap<Integer, Integer> map = new HashMap<>();

// 请保证arr中，只有一种数出现了K次，其他数都出现了M次
public int onlyKTimes(int[] arr, int k, int m) {
  if (map.size() == 0) {
    mapCreater(map);
  }
  int[] t = new int[32];
  // t[0] 0位置的1出现了几个
  // t[i] i位置的1出现了几个
  for (int num : arr) {
    while (num != 0) {
      int rightOne = num & (-num);
      t[map.get(rightOne)]++;
      num ^= rightOne;
    }
  }
  int ans = 0;
  // 如果这个出现了K次的数，就是0, 那么下面代码中的 : ans |= (1 << i); 就不会发生
  for (int i = 0; i < 32; i++) {
    if (t[i] % m != 0) {
      ans |= (1 << i);
    }
  }
  return ans;
}

解法二：更简洁

public int km(int[] arr, int k, int m) {
  int[] help = new int[32];
  for (int num : arr) {
    for (int i = 0; i < 32; i++) {
      help[i] += (num >> i) & 1; // num在第i位为1
    }
  }
  int ans = 0;
  for (int i = 0; i < 32; i++) {
    help[i] %= m;
    if ((help[i] %= m) != 0) { // 第i位上，有1
      ans |= 1 << i;
    }
  }
  return ans;
}